Very very common issue that I guess everyone has fallen for at some point or other.
In your spellbook, in the General tab is an ability called Fishing. It’s this you need to click on in order to fish. Drag it onto one of your action bars.
What many people do is drag the icon for their fishing rod onto an action bar, or just directly click the rod - this doesn’t work and just results in an error message.