Mines do not appear naturally. You have to make them yourself.
Find a rock face, use your pickaxe and rt click to Prospect. It will tell you if anything is nearby. You want to find Iron to start with.
Once you locate some ore, find a rock face close to it that has a slope of 15 or less on either side. The closer they are to the same slope the better the entrance will come out.
Use your pickaxe again rt click>Mining>Tunnel and after 20-30 hits (depends on your settings in the server) a mine entrance will appear.
Once you have this you can mine Down, up or straight (mine) to move around inside.
Do Not make large rooms, dig in straight lines with side tunnels going around 2 tiles. this way you keep the mine more stable while covering as many tiles as possible.
If you find a lot of good stuff you may want to eventually reinforce your entrance and intersections from collapsing.
Best of Luck!