Is there a way to find where other players are in the Minecraft world without asking them for their coordinates?

Yes, you can share a map item on a multiplayer server.

If you have a map, you can "clone" it to create an exact duplicate. It will show the same explored area on each clone, and all players who are using the map can see player arrows for each other. I have tested this with my brother on our server.

To clone a map, put the Map item to be cloned and one or more Empty Maps in the crafting grid. You will get 1 clone per Empty Map.

For more information, see: http://www.minecraftwiki.net/wiki/Map_(item)#Cloning

No, not without mods (and even then this is functionality most modders don't care about creating). You're going to have to hunt them the old-fashioned way.

Look for signs of passage: half-harvested trees, temporary shelters, mined ore, cobblestone. Lay traps: place tempting things and wait in a camouflaged spot. Find their base(s).

My Bukkit plugin Mapcoords has a command /mc find [player] that will tell you the coordinates of a player.