Double-click on a fishing pole, then click on a body of water. If successful, you will catch a fish.You might catch something more interesting than a fish. Success with this skill also depends on the availability of fish in that specific area.

0-65 - On land you will fish up Footwear, Magic Fish, and Normal Fish.
80+ - Sea Serpents (No SoS Message), Special Fishing Nets.
90+ - Treasure Maps 95+ - You can reel in Big Fish which can be used to make Trophys via Taxidermi Kits.
100 - Messages in a Bottle (aka MIB) / Waterstained SoS Message
100 - Ancient Messages in a Bottle (1 in 20)

You can get to 100% fishing on land, but deep sea fishing gives much faster skillgains.
Monsters will never spawn by fishing from land.

Note: Big fish are often used in player run fishing contests and will come stamped with the weight, angler name and time of the catch.

Note: You must attend any fishing while at 100 fishing. Fishing at this point will be monitored by the attended verification system.

Gideon's Advice: You can gain to GM Fishing easily from any coast or dock even without moving much because the water tiles will respawn relatively quickly and you can reach 2-3 different spots from where you are standing. You will begin to see the AFK macroing gump at this point and will need to start attended macroing fishing in the ocean.