How do I uninstall this?

Has he tried uninstalling whatever software he loaded? Some software is good about including an Uninstall. Other software has to be taken out by brute force.

There is also the option to do a system restore after manual attempts to remove the software have been done.

You might see if he can right-click on the menu bar area to temporarily disable the new toolbar.

There are other options as well for removing a toolbar.

What did you do to get rid of it?

You want to make sure it doesn't have anything running in the background. Check task manager or use a process explorer.

Adding to Alleycat's comments:

Your father probably downloaded some program that came with the toolbar. A lot of freeware does that now a days (most that I encounter, that's not open source), that's why you want to go through the custom setup and untick all the boxes you can.

I recommend RevoUninstaller (free). It can find programs that windows uninstaller can't, and removes everything related to the program. See if it'll find the toolbar, and make sure you go through the ultimate removal step, checking all the boxes and deleting anything it'll find after the uninstall.

A lot of the freeware archives now seem to have a nasty habit of repackaging stuff with toolbars and adware that there's no way to opt out of during install. Be very wary if a program isn't direct from the author, or from a generally-trusted repository like SourceForge.

Some of the Adobe software auto checks an option to install a toolbar whenever you update. You should ask him if he updated anything.