On Linux, Alfresco installs into a single directory. If that directory is /opt/alfresco, for example, you can completely uninstall the app by recursively deleting the entire directory, like "rm -rf /opt/alfresco".
BE CAREFUL. This will completely delete the installation, and if your content store is in a directory within that tree, in /opt/alfresco/alf_data, for example, all of your content will be lost. Similarly, most people use a standalone database server, but if you've let Alfresco install its own PostgreSQL install, then its data will also be in the /opt/alfresco directory tree. So you might want to be more surgical about it.
For a complete uninstall, including deleting your data, you'll also want to drop the alfresco database.
In your question, you mentioned you are installing a new version. If so, there really is no need to uninstall your current version at all. The safer approach is to install the new version along side the old, then just point the new install to your old content store and database.
For example, I always install alfresco into a version specific directory, like /opt/alfresco-5.2.5. Then I create a symlink called /opt/alfresco that points to the version specific directory.
When it is time to upgrade, I install into /opt/alfresco-6.0.1 and move the symlink. This has the nice benefit that any config that was pointing to /opt/alfresco in the old version won't need to be changed in the new.
Once the new version is up-and-running with all the customizations and configuration and everything is cool, only then do I go back and delete the old binaries, being careful not to whack the content store or the database data if it is there.