I just bought a new graphics card and with buying it my CPU fan during games spins really fast and makes heaps of noise. I am assuming that since i have a better GPU and can run games on higher settings the CPU is using more power? Therefore more heat? Would you recommend getting a new cooler and if so what is a good air cooler for the FX 8350?
Depends on your case and budget really. I had a bad budget case before and I ate a restocking fee from Newegg. The liquid coolers like a Corsair H60 wouldn't be a bad choice. If not, the time tested Cooler Master 212 is always a winner. Needs 160mm+ for clearance though.
If your case can handle it I would suggest the Cooler Master Hyper 212 EVO it is a really good air cooled heatsink. After having two pumps go out in two Corsair H100i setups I can't suggest them any longer. For water cooling I would go with a full water cooling loop like a XSPC EX360 or such. In my opinion they are much better than the AIO water coolers.
If you are running the stock heatsink/fan the yes they do tend to get quite loud as the heat ramps up. They are OK for light task but not so as you task the CPU.