So I've been re-texturing a bit, had some fun with that, but now I want to get to the next step: making my own model, or at the very least somewhat modify Bethesda's.

Where should start?

I myself started modelling with Blender. http://www.blender.org/

It's free and you can make some extremely complex models (see the gallery), even animations too. However, I'm not sure if the file types are the same as/compatible with the types used in Skyrim. Overall though, if you're just getting started Blender is a fantastic tool.

You'll still need some tutorials and stuff (which can be found on Google and the Blender website), but after getting the basics down just experimenting is the best practice.

Okay, thanks!

If you try Blender, you'll need the Nif Scripts. Last time I checked, the Nif scripts only worked on versions 2.5 on down. 2.6 was an overhaul of the UI, and Nifscripts never worked for me
Also, if you try animation, you'll want to visit this thread http://www.gamesas.com/topic/1336657-rel-havok-animation-converter-thread-2/
Which is the way to convert Skyrim's animation to something Blender can import, then convert it back. From my understanding anyways... I haven't tried it yet.

Also, you may want to look up "Blender noob to pro", its a tutorial that explains a lot.

You can get 3dsMax for free if you have a .edu email address through http://students.autodesk.com/.

Actually, it was working on 2.4x, and 2.5 & higher are overhauls not only UI but much more then that.
There are some nice tutorials for starters by Mr_Siika on TES Nexus and Vince on TES Alliance.

Only use Blender as last resort IMO

It's UI is overly complex, its a non-standard modeling editor, and Maya/3DS Max are much more robust, easier to use (to a certain degree..) and are modeling standards.

However, they are also very expensive. If you can't find a way to get it for free (if you are a registred student to sign up for a student edition on their website for example), then blender is the best you're gonna get 3D modeling wise.

I'm pretty sure you need NIFscope and such too, since Bethesda likes to use an extremely old and outdated modeling format for their games. You should be able to import objects you make in the above editors into nifscope and convert them into the proper format.

I'm somewhat familiar with NIFscope already, used it a lot for my textures, but not in depth.

Speaking of which, any guide or tuto to open a nif file on 3DS, which I acquired free-ly with the student thing (yay students!) but now I just want to slap some under-armor to the Ancient nord set, because honestly, the revelation on both model is absurd.

I am HOPING adding some clothes isn't hard, right?

So to get a model from Blender into Skyrim, you would need to export it as what format, then load it into NIFScope and do a lot of tweaking?

Have to echo the sentiment as using Blender as a last resort, especially since the plugin to get it to play nice with Skyrim is a bit outdated. Blender has a friendlier user interface now, but not back for the version most compatible with the plugin.

3ds max seems to be easier for beginners.

Always wished there was more modding community support for Zbrush, though. Now there was a nice little program that had been free for awhile.

If I wanted to take the frost rune explosion nif, and make it red instead of blue, would I do that using nifscope to simply find the textures and then change them?