Between work and home I'll surf the web on one of many Windows, Linux, or MacOS X machines. A few years ago I used to be able to keep my bookmarks synchronized using Netscape and an Apache mod. My only requirement was that it be through an interface that's always present while I'm browsing so I can easily add a new bookmark. That pretty much eliminates those web sites that let you store bookmarks through a web interface.
I've finally found a solution that works for me with Firefox: the Bookmark Synchronizer. What a relief. Now I can add a new bookmarks on any machine and when I switch to a different machine, they're there. It supports an XML format called the XML Bookmark Exchange Language (XBEL) so I'm hopeful other synchronizers will eventually come out for IE, Safari, etc…
For you folks wanting a more cross browser solution, another alternative I played with for a bit was the Yahoo toolbar which does synchronized bookmarks as well (albeit through the toolbar and not the browser native bookmark interface). The Yahoo Companion For Firefox supports that as well. So with that you could at least switch between IE and Firefox, although why would you want to? 
[...] I use a slew of machines so keeping my bookmarks and files synchronized between them has always been a priority. I’ve had the file synchronization issue under control for a while now by putting my documents and such into subversion but only twice did I have a good solution for bookmark synchronization. The first time is when Netscape included built-in bookmark synchronization via WebDav in the late 90’s and then 2nd time was in Firefox 1.0 using bookmark synchronizer (no longer maintained). I’ve finally found another solution and so far I’m digging it! [...]