I just
released my first stage and it was built using all custom art. I pulled most of the information on how to do this from random tutorials in the KC:MM forums.
Some of the more useful ones that I found were:
Guamboy27's Stage Making Guide
Guide to Stage Builder Block Based Stages
If you're a Maya user (like me) then you'll also want this tutorial to show how to properly import models to your stage.
Rigging and Importing in Autodesk Maya
(Yes, I know that guide is written for characters, but for the most part the process is the same. Just skip all of the weighting and such done during the rigging process.)
That being said, I'm still new to this world as well. Your best friend will be the search box on KC:MM. The forum is riddled with extremely useful posts about how to do whatever you are trying to do. I always just search for the things that I need within that forum, and 9/10 times I'll find something that helps me there.
Also, that second link I posted, it has a link to a .pac file that is pretty much empty, but is ready for you to start modifying. It was insanely helpful to me to have an blank slate to start with so that I know what all exists in the stage file and what I can remove.
Best of luck man, it's a lot of work but it's pretty cool to get your own custom content running in the game.
I spent a month on the art for this stage, and around another month trying to learn Brawl's engine and figure out how to get content to work properly with it.
For your first project I wouldn't suggest something quite as ambitious as what I have put myself through. I approached this process from the perspective of an already competent Environment Artist with a lot of knowledge about other game's engines and such, so don't feel discouraged if you aren't picking things up as quickly as I managed to.