I say cross your fingers because you don't have a very high chance of pulling up fish when you are level 0; most of the time you will probably see, "You lost your catch." Hopefully that message will be accompanied by, "Your fishing skill raises 0.2.", but don’t count on it. Skillups are few and far between. You have a much lower chance at getting a skillup in fishing than you do in any other craft, but that is because you can fish a lot more and you get paid to fish.
Sometimes when you try and pull up a fish high above your skill level or an item (like a Rusty Bucket) that is too heavy, you might break your fishing rod. This isn't fun, but it happens. You can, however, repair fishing rods; but with the fishing rods used at low levels, it is not economically worth it. You can try and sell the broken ones on the Auction House, or just sell them to an NPC. Go ahead and buy another Bamboo Fishing Rod (or a different rod of your choice) so that you can try and get more skillups and fish. Even with the chance of breaking your rod, you should be able to cover the cost of a new one with the fish that you catch. If you enjoy fishing, you can look to invest in a better fishing rod. For more info on rods, please see Fishing 110: Rods and Bait. Don't just dive into an expensive rod at first, because if you break that one, you will probably be kicking yourself for a while.
That should get you started on fishing. Test out the waters and see if you like it. Fishing can be tedious to start with, but bear with it for a while because it can be very profitable later on. To help you get through the levels, try getting a few fishing buddies so that you can talk to them and fish at the same time.
Every time you reach the *8 level of each rank, you will be able to turn in your next item. This item always goes to Thubu Parohren. The following is a list of the items needed and the rank you will be given for each: