Ubuntu: How can I uninstall software?

If the application has been installed via the package manager, all you have to do is run

sudo apt-get remove <application_name>

That should always work. If the terminal isn't what stirs your tea, you could open System → Administration → Synaptic Package Manager, search for the package you want to remove, click on the checkbox next to it and select "mark for removal". Once you click "Apply", the package should be removed. There's of course also the Ubuntu Software Center. It's pretty much the same thing as Synaptic. Just search for the application name and click the "Remove" button.
Sometimes applications can be split up into multiple packages (for example, many games have a separate package for their music). To make sure that you uninstall all related packages AND configuration files, you can type

sudo apt-get purge <package-name>

or -in Synaptic- "mark for complete removal" instead of just "mark for removal".
As for applications that have been manually compiled and installed, there's not always a single way to remove them. The best thing to do is consult the README/INSTALL file that accompanied the source package - if one exists.
 

-----------------------

• The software centre: find the package, click remove
  
• Synaptic : the same
  

---

• apt-get:
  

  sudo apt-get remove <package> && sudo apt-get autoremove
  

• aptitude:
  

  sudo aptitude remove <package>
  

It's important to note that when you install things, they often depend on other packages. When you fire off apt-get remove <package> it doesn't remove the automatically-installed applications by default. This is often safer (if you're temporarily removing something like ubuntu-desktop) but this can mean you end up with a load of cruft.
aptitude will automatically remove things (as well as having a nice interactive command line interface)
You can also search for cruft in synaptic using the "local or obsolete" filter under the status section.