Trying to display Parent Category as header for Sub-Categories

Hello --

I recently dove headfirst into the world of Wordpress, Atahualpa, CSS and PHP, so I hope my question here makes sense. I have been trying to accomplish as much as I can within the parameters of the Atahualpa theme, and I am hoping this won't be too difficult.

I have set up my list of categories, and I also have many sub-categories (children). So, using the common example I have seen on other threads, I have:

Fruits
---apples
---oranges
---bananas
---strawberries

Vegetables
---carrots
---celery
---onions
---turnips

For each post, I assign the relevant children categories. For example, Post X will be assigned Apples, Bananas, Carrots, and Onions.

When I display a post on a page, I would like to display each relevant Parent Category first, followed by a semi-colon, and then the relevant child categories. In other words, I would like to display the following in the footer for the example above:

Fruits: Apples, Bananas
Vegetables: Carrots, Onions


Right now, it just displays:

Categories: Apples, Bananas, Carrots, Onions.

So, I guess I need to set up some PHP script that says something like, for each category parent, if child categories are present for that parent, then print "Parent Name", followed by a semi-colon, followed by all relevant Child Categories.

I think this seems possible with some of the category functions, I just don't know enough about all this and can't seem to find anything in the threads.

Thanks for any help!