It is a long, slow process. I should know
Basically just be transparent with your users and they will likely give you a try and slowly build more trust.
Many start by just sending 1 coin, and then withdrawing it immediately - out and out scam checking. Then they may send the coin back, bet it, and if they win withdraw it immediately. Then slowly they will send larger amounts, checking the withdrawal system often, making sure bets/payoff amounts are exact, etc.
Getting a few positive reviews in the forums or other bitcoin related sites helps (http://www.bitcoinbulletin.com/2011/03/13/bowling-for-bitcoins-meet-the-trader-02/
- seemed to drive some users) - even just a simple 'Ya, I won and I got paid' can really help. Eventually people will start sending 10,50,100 coins or more if they like your service.
Good luck with your site.