I downloaded and installed WiX 3.5 and, from what I understood, the templates for WiX projects should be installed and available when I try to make a new project.
Did I miss a step somewhere?
On the New Project Dialog, there should be an entry in installed templates call Windows Installer XML.The types of project are listed under there. I did nothing special, just run the installer, if they are not there try a repair. Wix 3.6 is out now if you can move to that.
Update: Based on your last comment I did some more digging, it would appear that you are right, Visual Studio Express does not support Votive, which is the Wix Addin.
See http://wix.sourceforge.net/votive.html
It says the following:
Votive will not work on the Express SKUs of Visual Studio
I guess the alternative would be do use the command line tools, which would probably take much longer.