First you need to understand what a wallet is. That way you can decide how you'd best like to store it.
A wallet is basically a password & an associated address. That password & address can be generated entirely offline. Imagine some function f(x) such that f(x) is easily calculated from x but x can not be obtained from f(x). In such a case, f(x) would be like your Bitcoin address and x would be your password or private key. In order to have your wallet, you're going to need to save your private key.
Its basically up to you where you store it, but if anybody gets your private key, they will have your Bitcoins. There is no other way for them to get them, so unless you're typing your private key in or something, they will not be able to get your private key with JUST a keylogger, assuming you're using a normal wallet on your computer.
The way Blockchain.info & other good web-wallets work is it stores your private key, encrypted, on their server. When you want to use the key, it passes it to your computer, your computer uses your password to decrypt it, and then you can use the private key as if you had it all along. The upside of this is that you can't lose it if your computer crashes and can access it from any computer, not just one with the key stored on it. The downside is that it renders it easier to hack, since if they get your password, they can ask blockchain.info for your encrypted key and then use your password to decrypt it.
What in my view is the best of both worlds is a deterministic wallet like electrum. In this client, the key is stored on your own computer, and not online. This reduces the risk that somebody can get it. However, the key is derivable from something called a seed, which is basically a group of english words. This means you can get your key(s) from that seed if you remember that seed or write it down, even if your computer is wiped. The only way that a hacker could get your private keys from electrum is if they got a virus on your computer that stole your password when you typed it in AND stole the wallet file on your computer.
If you want to be absolutely safe, then get a cheap offline computer (netbook or something) and install electrum there. Create a brand new wallet there, and store all your coins on that computer, memorizing and/or writing down the seed. Send all your Bitcoins to that computer. When you want to spend your Bitcoins, sign the transaction offline, and copy the signed transaction hash, stick it on a USB, then use an online computer to push that transaction hash to the network (or use something like Blockchain.info). In this way, there is no conceivable way anybody could get at your Bitcoins, even if they had a virus that gave them full control of all of your computers. Also, even if somebody took a sledge hammer and bashed the hard drives of all your computers, thanks to your seed, you could still restore your wallet. On the other hand, it might be easier to simply stay clear of viruses and sledge hammers
