Is there a way to find where other players are in the Minecraft world without asking them for their coordinates? I play with friends. We've sort of aligned ourselves in a 2 vs 2 match-up, and since we wanna PvP with them, we need to find them first.
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).
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