Not sure why you would get 404 on yours, it works by default, and I added location to mine.
Working example:
http://www.detelli.com/Results.aspx?c=46&houses_for_rent_in=bothell
Which you can change bothell to seattle or any other city.
I set my site up, so all the states are categories which is what the c stands for.
As far as craigslist goes, it looks pretty simple, all they did was build a master list filled with the links to all the states and such.
And had the links setup as subdomains.
Look at your host provider for how to add subdomains.
I'm not sure how craigslist remembers your preference, they don't seem to be loading a cookie, and that's what I would expect.
But subdomains is your answer.
Please remember to click “Mark as Answer” on the post that helps you.
This can be beneficial to other community members reading the thread.