SortPlaces is a Firefox extension that allows you to sort your bookmarks in different ways. The Bookmarks Organiser within Firefox does have some sort options, but these are not permanent and the options are not very useful.
SortPlaces is designed to work with SyncPlaces to automatically sort your bookmarks when you synchronise them. This is one of a number of extensions I've written that you may find useful.
July 13th 2010 - SortPlaces v1.6.8 released: Updtaed to support Firefox 4.0. Added Chinese (Simplified) locale.
January 12th 2010 - SortPlaces v1.6.7 released: Reversed the meaning of the include/exclude options, so they make more sense to more people. Added Danish locale.
November 23rd 2009 - SortPlaces v1.6.6 released: Bug fix: Fixes infinite recursion issue and now properly deals with missing or bad starting folders.
November 11th 2009 - SortPlaces v1.6.5 released: Updated to support Firefox 3.6
You can sort using the status bar icon, an option in the Bookmarks menu, the Tools menu, the Bookmarks Organiser, and a toolbar button:
There is also an option to automatically sort your bookmarks whenever they change (see below)
You can set the sort ordering using the Options dialog, which may displayed using the link on the Bookmarks menu, or by right mouse clicking on the status bar icon (shift-click, command-click, ctrl-click, meta-click etc. will work just as well), or by using the Options button in the Tools>Addons menu item.

You can set different sort options for the Menu, Toolbar and Unfiled bookmarks separately, and for each you can set two levels of sort, and the order of folders, bookmarks, queries and livemarks.
On each tab use the dropdown to select what you wish to sort by. You can also select 'Unsorted' as the 'Sort by' option and your bookmarks will not be touched. Bookmarks, folders etc are normally sorted in increasing alphabetical or numerical order depending on the option chosen. You can use the 'Reverse order' option to change this. Sorting of Names and Descriptions is normally done in a case sensitive way, e.g. 'a' comes before 'A'. But you can use the 'Case insensitive' option to completely ignore this when sorting (i.e. 'a' == 'A').
When sorting occurs you can decide whether to group items of the same type together and how they are ordered using the 'Folder ordering' options. Change the numbers displayed to decide how you wish to group and order the four bookmark types. The numbers represent the ordering with a lower number meaning a higher position in the order. For example if you wish folders to always appear before queries, and queries before bookmarks, with livemarks grouped together at the bottom, then set 'Folders' to '1', 'Queries' to '2', 'Bookmarks' to '3' and 'Livemarks' to '4'. If you wish two or more items to be treated equally and not grouped together, then set the order of them to be the same, e.g. set both 'Bookmarks' and 'Livemarks' to '3'.
Note that bookmarks/folders/etc. are sorted within groups divided by separators. So if you have a separator in the middle of a folder, all the items above the separator will be sorted independently of all the items below it.

You can sort manually as described above, or set the 'Sort automatically' option, which will silently sort your bookmarks whenever they change. The sort actually occurs when there have been no bookmark changes for a certain time. This 'delay' prevents unnecessary sorting when you're making a lot of changes, it also prevents the auto-sort interfering with certain bookmark operations that can take a while to complete (e.g. when adding a new folder the folder's name may be committed or cancelled by the auto-sort before you've finished typing it in). This delay (in seconds) may be amended using the 'Delay' option, either reducing it (minimum 3 seconds) if you want the sort to occur quickly after making changes, or increasing it (maximum 999 seconds) if you find the auto-sort interfering with other operations.
The 'Sort folders separately' option allow folders to be sorted in a different order to other items. When you select this item a new tab will appear on the 'Sort order' page allowing you to separately select the order you wish to sort folders by. Only select this option if you are going to make use of it to avoid any side effects.

By default all your bookmarks in every folder are sorted. But if you unselect the 'Include all bookmarks' checkbox then you can use the 'Select folders' button to choose exactly which folders you wish to sort. Use your mouse and/or keyboard to navigate the tree and highlight the folders you want to include. Similarly if you unselect the 'Exclude no bookmarks' checkbox then you can use the 'Select folders' button to choose which folders you wish to exclude from the sort. Note that the 'Tags' folder and it's content will be ignored if you select them. (Unfortunately, Firefox doesn't provide a simple way of excluding the Tags folder from the folder display).
Finally, there are options to allow you to display the SortPlaces options in various Firefox menus and on the status bar, if you so wish