I typically go double scout. Recon is really important to me and I need to know what's going on in the map around me fast and keep my eyes on the surrounding fog (perhaps I play too much RTS). Also, once I get a trireme, I explore the coasts as well; sometimes with two of them.
I use my initial warrior to just explore in a small radius around my capital to reveal the surrounding terrain and to take advantage of any ruins that have spawned near me. I keep him close so that afterwards I can send him back to the capital to clobber any barbarians that wander towards my city and also to escort my first settler.
The first scout is doing the same as my first warrior and exploring all the terrain in a wider, further radius around my capital. This way, I can better plan out my next couple settlements and I'll know how many unique luxuries I'll have available. Once that's finished, I just beeline out in one direction as my second scout goes in a different direction for some deep exploration.
I believe in Civ5, exploration pays a lot more than in previous games. Ruins never spawn hostiles anymore, and just grant various positive things. You can rake up a nice amount of gold by contacting city-states, which is also nice for future quests (ones you sometimes don't even intend on fulfilling and you just fall into them anyway and receive bonus influence -- they're good contacts to have laying around as the game progresses). Extra happiness is definitely nice if you find any natural wonders. And since the fog of war updates as borders expand and cities are settled, it pays even more to fog bust (cloud bust now?) since you can keep your enemies in check. It's also nice to get more trade partners since you can't trade contacts and either have to find them or wait for them to stumble upon you.
Oh, and with religion now, exploration can pay even more since it can really kick start your path towards a pantheon and prophets, since religious city-states will also reward faith on contact and ruins have a chance for some nice faith bonuses.
If all those things weren't enough, I personally just get a real thrill out of exploring the map and seeing who/what's out there -- it's a fun part of the game for me. Dodging barbs is also a fun little game itself.
