How is it possible that when you have Facebook chat open (in the browser), when you continue to navigate Facebook it the chat never goes away? It's all in the same window. Do they control the load order or something to make it seem like it never went away?
I've implemented a few of these. There's actually several ways you can go as far as data storage. Databases are probably the most flexible and easy-to-use, but careful construction of the table and database itself are necessary to prevent the Bottleneck to End All Bottlenecks in high-traffic systems.
A quick and easy alternative is a simple text file, one for each chat "room" for each user. Using PHP logic, append whatever messages come in onto the end of this file. In your AJAX update logic, when a particular user's browser checks for updates, send the contents of the file downstream to the user and empty it. This does not store chat histories, but it does allow a relatively simple (if hard-disk intensive) file-based implementation.