I'll chime in a little bit because I think this is an area a lot of people are clueless on, me included (well, I was when I started).
I started out trying to figure out how to add high score tables to the levels in my game, and that turned into adding a whole online component to the game that includes; high scores, in game friends lists, in game mail, in game level creation sharing, and syncing across multiple devices (game is for PC and mobile).
Here's a bit of the nuts and bolts;
Using Gamemaker Studio for the engine, which actually makes this kind of database communication very simple. I went with hosting at the time (~2 years ago) that was affordable and worked, x10 hosting but your mileage will vary. The key was finding hosting that included mysql databases and an easy to use control panel with phpmyadmin installed.
Gamemaker has a simple http_post function which I use to send/receive data from my tables. How you store/organize this data will be up to you, but I can answer more detailed questions on that front.
Now, onto bandwidth and costs; right now I'm just paying for the most basic of hosting for my provider at ~$75 annually, but I have the option to move to my own dedicated servers at an additional $20/month and up. I'm right now only seeing a few dozen players per day, but I really don't know what to expect when I launch the game in May (only in beta currently). I'm using on average maybe 500-800mb a day in bandwidth with some days less, some days more, this is including the game's website as well.
I'm not sure what type of game you have in mind but short of it being realtime multiplayer, any kind of asynchronous or high score type multiplayer components shouldn't have huge scaling issues (I hope). If anyone knows any better and has actually launched a game with many (1000+) users asynchronously connecting to their database at once please share!