To use bait right click on the bait in your inventory and then your cursor will glow, then left click on your fishing rod (it can be equipped or in your inventory - doesn't matter).
Once you're fishing skill gets high enough you'll be able to start fishing in the little whirlpools you see along the coastlines and in rivers and lakes - those pools let you catch special fish that can be used in alchemy or cooked into better food using the cooking skill.
If you see a small pile of boxes and barrels floating in the water instead, by fishing in that you'll get boxes that you can open with stuff inside - usually cloth of some type, occassionally ore or metal bars and once in a great while a green item (as well as some pocket change).