You talk to those "random men" to trade Spheres. They will offer goods only in exchange for a Sphere of a certain kind and size. So, if they ask for a Red Sphere 39, give him a Red Sphere that's size has reached 39 or more.
The Underground map is based off of the Sinnoh Map. Take a look:
You would use the Explorer's Kit where the tunnels actually are. For example, the tunnels near the top right can be accessed when you drop down from Fight, Resort, or Survival Areas. The bottom left can be accessed by dropping from Canalave, Sandgem, and Twinleaf Towns / Cities. Drop down above the tunnels. Use the maps for help.
There must be something wrong with the game. Try describing it a bit.