"It's a HP ProBook 4530s, Windows 7"
Cleaning the fans doesn't seem like a terribly hard operation, have a look at a video like this and see if you think it's manageable.
You can even just blow on the fan, while holding it as he shows, and that'll help shift any fluff that's in there.
"Would you not suggest a cooling tray BadgersPaws2"
For people who use laptops on their laps they're not a bad a idea, but if it's being used on a hard flat surface the benefits might be slight. A computer should be able to deal with the amount of heat that it produces, this one isn't, so I think that there's something to fix somewhere.
Is the laptop always used plugged in and how old is it? It might be the battery, as they get older, especially if it's always plugged in, they can get less efficient and they can generate a lot of heat. Heat that is above and beyond the "normal" expectation for the laptop. What's the battery life when running from a battery? It might be worth taking the battery out entirely or getting a new one.
"Downloading a program to analyse the fans sounds good except I'm quite wary of downloading things like that"
I can't recommend one for a Windows PC. I've used them before on an old Apple laptop to great effect.