
The first solution attempt was right-clicking a .tm file, going to "Properties -> Open With" and changing the default application to GNU TeXmacs. This was a disaster, since now *all* plain text files would be opened in GNU TeXmacs, since Nautilus genuinely believed a .tm to be the same as a .txt and thus changed the default application for all text files.
My second attempt at a solution (after googling a bit) was checking the MIME file type associations, which is the way Ubuntu associates an extension to a file type. The info is all in the file /etc/mime.types. However, to my disappointment, this file already contained a mime type for TeXmacs documents, indicated by the entry
"text/texmacs tm ts". So even though the mime type was correctly recognized, it seems Nautilus wasn't picking it up. This could be further deduced from the fact that running the command file on a .tm document in the terminal returned the correct mime type.
After more googling, I finally discovered that this is in fact a bug and found a fix for it:
http://savannah.gnu.org/bugs/?25938#discussion
Essentially, you manually create an xml file describing the TeXmacs mime type to /usr/share/mime/packages and then manually update the mime database of the system (setting an icon for the file type is optional, but may be useful).
NOTE: the original poster of the above bug fix made a small typo: an extra semicolon (;) at the end of the line containing "mime-info xmlns=" Remove it before trying to update the mime database.
After this is done, logout / re-log (or simply kill / restart nautilus from the terminal) and the new file extension should now be recognized:

The nice thing about this is that it should conceivably work for any other file type that has a correct mime type in /etc/mime.types but is not being recognized by Nautilus.
Hope this was helpful ;).