If you are comforable with coldfusion and have the money to poney up for flash remoting I would go that way. It is probably the tightest package for tying flash to a database.

Remoting for Java and ASP.net works to, but in my experience cf is the way to go if you are just learning server side scripting.

With MX2004 though there is now pretty good support for web services so you could build webserivces to access a database and go that route directly from flash but then it depends on how much access you have to the host server, I doubt many ISP's will let you put a web service on their servers.