How to theme categories on a node edit page?

I find it not so easy to theme categories on node edit pages. For example, if I have a group of input fields for location, where "City" is a CCK text field and "State" is a vocabulary, I don't know easy (standard Drupal) way to put "City" and "State" close by; there could be other vocabulary fields that are not related to location and should be placed apart from "State".

I have been resorting to kind of hacky approaches such as javascript to manipulate/relocate fields on client side, which works but I can't help feeling there must be a better way.

Can you suggest a good practice (or module) of theming categories on node edit pages (and also on view pages)?