If the branch predictor is placed in the fetch stage then how does it know that the current instruction is actually a branch before trying to predict its outcome? Is some (very little) decoding already done in the fetch stage before going to the actual decode stage?
There is no decoding done in the fetch stage. The fetch stage relies on the Branch Target Buffer (BTB) to tell it which instruction addresses have had taken branches in the past.
The BTB is a small highly associative structure. It performs two functions. First it tells you which instructions are and are not branches. If the current program counter (PC) is in the BTB then the instruction pointed to by the PC is a branch, and the BTB will tell us the target of that branch and the branch predictor will give us a guess about whether the branch is taken or not taken.
If the current program counter in not in the BTB then either (a) the current instruction is not a branch or (b) we have never seen this instruction before (and don't know whether or not it is a branch, but we'll assume it is not or (c) the current instruction is a branch, but we've never seen the branch taken, so we've never put it in the BTB.
This last function (branches that are never taken are never put in the BTB) makes the BTB actually a very effective branch predictor. Branches that have never been taken are unlikely to be taken in the future, and the BTB predicts this correctly. Branches that have been taken at least once in the recent pass are slightly more likely than not to be taken in the future, and the BTB reflects this as well.
The BTB effect was rarely taken into account in academic branch predictor research done at the end of the 1990s (nor is it taken into account in the statistics in most textbooks). For most programs on most architectures the BTB actually filters out a significant number of branches (on the order of 25%) because they are never taken or rarely taken. For those 25% of branches you essentially get a 99% accurate branch prediction for free. The "real" branch predictor needs focus, then, only on the other 75% of branches.