Might add that the fishing permits are needed mostly for lakes and rivers. This due to bringing a little bit of money in for their preservation. Also many lakes have fish stocks replenished by adding farmed stock. But as Johan wrote, the cost is usually very cheap. Ranging from a few pounds for a day up to a tenner or so for a year's permit. If it's more heavily fished (ie. popular =) areas, it can go up a bit though.
As for what you are allowed to do and not to do, the Allemansrätt is a bit vague to say the least. Generally we use common sense as Johan also stated. There are however a few pointers that are good to make. You are allowed to cut down willows and bush (ie. shrubbery) but you are not allowed to cut down any living trees. Standing, dead trees are fine however and all fallen trees. However, you will note there are log-piles neatly stacked around areas where they cut down the forest for profit. Those are not free to take however and fall under the same rule as with living trees, you need the landowners permit.
When it comes to fire it's actually not governed by the Allemansrätt directly but rather by the fire regulations. During dry periods (ie. summer) general warnings are issued in different areas where there may be a danger for forest-fires. This is reported every weather-cast on the news and if you are uncertain, just call the firedepartment and ask. If there is a ban on fire in effect that means no naked flames so no log-fires. Alcohol/gas stoves are fine though, as are enclosed BBQ's in most places. Again if in doubt, just call the fire department and ask.
And when it comes to game and hunting, you need a hunters license and landowners permission for this. Exception might be tarmigan snaring up north where you still need a hunters license for but dunno about the landowners permission.
And you are allowed to walk around fairly freely. Note i said, fairly freely as there are places where you are NOT allowed to walk. Any military installation is off-limits and also any shooting ranges (Which usually are placed a fair bit out in the woods due to sound pollution) is off limit. So respect any signs / barriers that is there to stop you. In fact, a good rule is never to climb a fence. If it's allowed to pass into that area there will be a walkway into/over it if you just follow the fence. Reason being you might not like what's inside,if you want to outrun an enraged bull, go to Pamplona =)
Right that was a little collection of things to think of.
/HuBBa