1. Fix Your Migrations
The first thing you need to do is add the foreign key declarations to your migrations. There are several ways to do this. If you want to go old-school, you can hack the SQL directly into the migration file, but if you want to take a more classy (and DRY) route, I recommend Simon Harris' plug-in. The plug-in is very clever about figuring out the relationships automagically, but if necessary you can easily nudge it in the right direction.
2. Fix Your Fixtures
By default, Rails is going to load your fixtures alphabetically, and unless by some miracle that happens to be the correct order in which to load them without violating any referential integrity, you're out of luck. If you use Simon's plug-in, fixtures aren't going to present too much of a problem because it is smart enough to not apply foreign keys to the testing database. However, if you are like me, you're going to write some unit tests to ensure that the foreign keys are intact and operational, and all of those tests are going to fail. But don't fret. Again, there are a couple ways to solve this. The classiest of which is a little code hacking which lets you specify the order in which your fixtures should be loaded. (Will somebody please refactor this into a plug-in already!?) But if you want to go old-school and get your hands dirty, you can simply rename your fixture files, prefixing them with numerical values which coax Rails to load them in the correct order.
3. Fix Your Code
Rails and referential integrity don't always play nice together, so you're going to have to do a little massaging with your code. As I've ranted about here a few times before, one of the most frustrating is the way has_many handles the breaking of relationships. When you "delete" a relationship, Rails doesn't delete the record in the database, it simply nullifies one of the foreign keys, leaving an orphaned record. DHH noted in a response to one of my earlier rants that the reason for this is so the record can be reassigned, thus resetting the just-broken foreign key. However, if that happens to be a real foreign key in a database that enforces referential integrity, you're going to get a barf as the database will not let Rails set it to null. So, instead of deleting a relationship from a collection, you'll need to destroy the relationship itself. A minor syntactical semantic, but confusing and sometimes confounding nonetheless.
That's it in a nutshell. It's a bit of work to overcome a few little bumps in the road, and although it somewhat violates the Rails philosophy of database design, I think it's well worth it, and many of my colleagues tend to agree. As a shameless self promotion, note that I have whipped up a very crude plug-in to make has_many collections behave a little more intuitively (by my personal definition of intuition, of course) -- it should be backwards compatible so dropping it into your project shouldn't break anything.