Update, I'm going to describe my steps on what I did and how I did it to anyone who might be curious:
Ok, so I experimented with exportation to an .smd. Looked bleak at first, but I didn't give up. I just tried a normal export once the texture has been applied on the model in Maya but that didn't work and have me a gray model.
However, I opened some files and changed some stuff in them, but I don't think they had anything to do with anything. What I did instead was skimming through Milkshape and on the 'Materials' tab, below the two sliders is actually the path to the texture. So I loaded the texture I wanted to use there and then right-clicking in the 3D view and choose 'Textured' (almost at the top) I could see the texture on my model.
So afterwards I created a .qc file but I had to change the path to the texture and model inside it. I used the Nexuiz path, meaning where it says '$model' I changed that path to: 'models/ctf/flag_blue.md3'
I'm using the 'flag_blue' as it is hard coded by the engine and I don't want to compile my own.
I did the same thing where it says '$skin', there I changed the path to: 'textures/nexFlag_blue_diffuse.tga'
Then, after changing these settings in the .qc-file I exported the model to a .m3. Note, Milkshape will need you to name the .qc-file exactly like the model you're exporting to. With other words my .qc-file had to be named 'flag_blue.qc' if I wanted to export the blue flag.
Once that got exported I just simply placed the model in the Nexuiz folder (described above) and same thing with the texture. And viola, it worked. I didn't actually believe it to work so well so quickly.
Now down to the goodies:
Next up I suppose will be animations and whatnot.