Would it be fair to say that 'cold storage' is the way to go? I read earlier today that most users go with 'cold storage'
If so, can most clients work with this?
Any can be. The term cold storage defines an address that is created offline, on a clean computer. As long as the client does not require an internet connection to make an address, it can be used as one. Electrum, Armory, Multibit, Bitcoin Core will work. Electrum is my personal favorite though, visit this
link to find out more about Electrum.
When I want to change back my bitcoins to regular money, what do I do? These exchange things seem pretty unregulated.
Create an account at a reputable exchange (bitfinex etc.) and transfer your Bitcoins there. You might need to go through a verification procedure if their local laws say so. After that, just exchange it and you can withdraw it to your bank account. Most are regulated. Otherwise, you can try Localbitcoins.