This is a brief outline of the ways it can be done. There are many more in-depth examples on the web:
Set up you data sources in Coldfusion
Do as normal, but if you're using a MySQL version over 4, you must download the JDBC drivers. Follow this Adobe technote here
Design your CFC's
There are many ways in which you can connect to Flex. Flex Remoting or using Coldfusion / Flex connectivity (for this make sure you have all the latest CF updates for Flex 2 here).
Your CFC's must be designed to do the tasks required in an efficient way so that Flex uses the minimum of service calls.
Setting up Coldfusion for Flex Remoting
There are a few ways to set up remoting in Coldfusion, the simplest way is to set all CFC functions that need connecting to Flex i.e. to act as web services, to access="remote".
A more complex, but efficient way is to create a lightweight gateway CFC as an interface to the underlying CFC architecture. For example, consider CFC's called "MyService.cfc" and "MyGateway.cfc".
MyService.cfc contains all the logic you need doing: database queries etc. function access="public". Load this CFC into the application scope onApplicationStart, this way it is only intantiated one throught the whole application.
MyGateway.cfc is the remoting interface and contains no logic, it mearly calls the functions in MyService.cfc (now application.MyService). These function should be set to access="remote".
When you call CFC's from Flex (or Flash), a new instance of the CFC is created in memory on the Coldfusion server. If you call the full, bloated MyService.cfc each time you make a request you'll be using more memory than necessary, therefore the lightweight MyGateway.cfc is the one that is instantiated multiple times by Flex.
In Flex you need to use the HTTPService class/tag. Enter the URL for the CFC you want to call. Coldfusion will return a WDDX formatted XML response, which Flex components can parse and use natively.
This architecture is used and explained more on:
Using Coldfusion / Flex connectivity
Provided you've done all the updates. Create your myService.cfc as above containing all the logic. However, this time you won't need your MyGateway.cfc as you'll create equivalent classes in Flex which match MyService.cfc i.e. create MyService.as with all the same functions and arguments.
You can then instantiate MyService.as in Flex and use it just like any other object. This allows you to access all the backend power of Coldfusion via normal Actionscript function calls - pretty powerful!
My tuppence worth
Great and powerful CF/Flex connectivity may be, I'd personally use remoting for my Flex applications as this will make your Flex application platform independent.