How would you store a bitcoin wallet with the security of the wallet being a priority for a small bitcoin exchange? Offline wallets are the safest though how would a client be able to withdraw their coins if the wallet is offline?
The safe way for an exchange to function is the hot-cold wallet system. A hot wallet, which the server has access to and where all deposits and withdraws get handled from.
Function of the hot wallet
The hot wallet is what your exchange will you to receive and send bitcoins with. If you are sending bitcoins to a user for a withdraw, it comes from the hot wallet on server. If you are receiving, make sure the address in in the hot wallet. A good hot wallet only keeps a small portion of bitcoins available. An amount that allows your service to run for a week or even a day without running out. Say your hot wallet was 5%-10% of your total funds, you'd daily or weekly add bitcoins or take bitcoins. If there are no bitcoins on the hot wallet, your service should come to a grinding halt. You cannot automate the filling of the hot wallet from the cold wallet, this is dangerous and is exploitable.
The benefit of this smaller balance on the server is that you cannot get robbed of all your funds suddenly
The cold wallet
The cold wallet should not be in any way connected to your exchange. It'd be best if only you had access to it. 90% of your funds should be kept here. The idea is that the attacker cannot access 90% of your funds electronically or automatically. You should manually be moving coins from the cold wallet to the hot wallet by yourself.
Note: Do not take my advice here as full advice, you should look up proper wallet management, it is a broad topic. See the Bitcoin wiki article on Securing your wallet.