How to fish can be found - for free, even! - in the Merchant Halls where you'll need to buy your gear. The instructions are on the last page of the Crafting Vendor's inventory, in a book labeled something like Beginner's Guide to Fishing.
To fish, you do not need a crafter's license. However, you do need one if you want to do anything more with the fish you catch than roasting them over a campfire.
As to a loan, I'm sure you could post something in the tradehall, but as to your chances of getting one, I don't know.