I think you can make something nice and reasonably cheaply, especially if you can reclaim materials (nice way of saying find usable trash). This is also based on you having access to a few basic tools, such as cordless drills, bits, spade bits, circular saw, jigsaw, etc...
The first thing you'll have to consider is stability. There are 3 ways, off the top of my head, to secure a cat tree. One is to have a design that's small enough or wide enough on it's on that its not going to fall over even if your cat is swinging from the top. The second way is similar to the first. You can build it larger, but you'll build at least 3 bases to make it stable sort of like how a stool is stable with 3-4 legs. The stability would come from hooking them to each other. That would be more expensive, though, and take up much more room. You could conceivably build one in a corner and have good stability and wouldn't take up nearly as much room. You would put one base in the corner and run one leg down each wall.
The way I'd probably do it, though, is to anchor it. I would either put a bolt in a ceiling joist or a wall stud. You don't have to worry about it messing anything up, because if you ever decide to take it down, you simply remove the bolt, put some putty in the hole, when it dries you sand it flush, then hit it with a touch of matching paint. An alternate way is to use a plate, bolt, and nut to push against the ceiling. You would drill a hole slightly larger than the diameter of the bolt in the top of the cat tree, about 1/2-3/4 the length of the bolt in depth, and make the cat trees main post about 4" short of the ceiling. You can cut a small plate of the plywood you'll use for the platforms. If you have a spade bit or other bit the size of the bolt head, I'd make a slight counter sink. Then glue some felt to the back for protection of your ceiling. The way you'd secure it would be to run the nut up the bolt about half way, add a washer, and drop it in the hole. Put the plate on top of the bolt head and adjust the nut down, to force the bolt up and push the plate toward the ceiling. Again, you'll want to be under a joist and if you push too hard it'll crush the drywall. If you're not under a joist, you'll go through the ceiling and have a big problem. However, it'll be easy to install and move with this method.
As far as how to make it, you can get fancy or keep it simple. I'd use a 4"x4" for the main post. It's common, cheap, and is about the right size. For each arm, I'd probably use a short piece of 2"x4" cut from a regular length. To attach it, you can go as fancy as a mortise and tennon, you can use and L-bracket to screw it to the post and 2"x4" with screws, or what I might do is use the L-bracket, but then drill a hole through the 4"x4", counter sinking the backside and use a lag bolt to add extra security for a fat cat. It will really help with the stress of the weight at the end of the arm. As a note, anytime you're putting in a screw, from a decking screw to a lag bolt, you have to predrill the hole to prevent the wood from splitting, which looks bad and weakens the hold. To choose the appropriate bit for the hole, hold the bit up directly over the screw, you should be able to see the blades of the screw, but not the shaft. Another helpful tips is to buy screws for the bit you have, not vice versa.
One addition I just thought of is that you might not want your arms and platforms to be 90 degrees from each other. That might be a hard jump for a fat cat. If you want to decrease the angle, simply turn the 4"x4" so that one of it's corners is up and use whatever is handy to block the sides and keep it semi-steady. Then take your circular saw and make a 1" deep cut. Move over and make another about .5" over. Repeat till you have a series of cuts. You can then either use a hammer, or more cleanly a chisel, to knock them out. You can then use sand paper or carefully sweep the circular saw back and forth to smooth it. It doesn't need to be perfect.
This is a great time to mention you need to use all the safety precautions. Wear ear plugs, eye protection, gloves, etc...
So now that we have the main post, and the arms attached, you just need the platforms. You basically have 2 types of platforms on cat trees. Either a flat platform (sometimes with sides, like a nest), or sideways cylinder. The platforms are the easiest. Simply take a piece of 3/4" plywood and mark out the shape. You can free form it if you aren't putting sides on it. If you want sides, I'd do a simple rectangle. It will be very easy to attach the sides to this. If you free form it, you'd either have to make kerf cuts or steam bend some 3-ply. That's more work than it's worth.
The cylinders should be easy as well. Cut rings out of the plywood. You can probably get away with 3 rings. The inner diameter (ID) should be whatever diameter you want it for the cat, plus about 2" to account for the carpet. The outer diameter can be whatever you want, but I'd say make the rings 2"-4" thick. Then either use short lengths of 2"x4" or 2"x2" to separate the rings. Just use screws to attach them. So you'd have a ring with 3-4 pieces of 2"x4" attached like a stool with legs. Screw a ring onto the bottom of the legs. Add more legs, screw the other ring on. You now have a cylinder. I'd probably notch out the bottom to set on the 2"x4" arm and screw down through it to attach it. To keep the carpet from sagging, I'd probably glue and staple strips of 3-ply around the inside and outside like stripping to support the carpet.
To cover I'd try to find some used carpet. You can probably contact a carpeting company and either get scraps or get descent carpet they're pulling out of a home to put new carpet in. Either way, you need to wash it. Just wash it outside with dawn, a scrub brush, and a water hose. Hang it to dry. Attach it to the platforms first. Start with the top and glue it down, pressing it tight while you lay it down. Wrap it around the edges. To get it tight to the bottom, cut slits or triangles out of the material hanging below the bottom. Then put some glue around the edge of the bottom and pull the strips tight and push them into the glue. Once it sets, you can lay a piece over the bottom to cover it and it'll look good.
You can wrap the arms and post in the same manner. I would probably measure the piece of carpet and precut it. Then I'd glue, but I'd use nails to tack down the starting edge. I'd start on the bottom. Then wrap it and use screws and washers to screw through both pieces of carpet. You won't see it on the bottom or the back. You don't have to, though. The glue will hold fine.
I'd leave sections of the post without carpet. You can put it all over if you want, but I wouldn't use cardboard. I'd put a rough hemp type rope in these sections. Drill a hole at the top and bottom of the section you'll wrap with rope. You can do the math or just guess at the amount of rope you'll need. Pass the rope through the hole and tie a knot. Wrap the rope around the post, pulling as tight as you can and making sure the rope is pushed against the previous wrap. When you get to the top, make sure you have 6-8" of rope left. Keeping the wraps tight, feed the rope through the hole. You can pull it tight and tie a knot. This will tightly secure the rope and make it easy to replace if the cats shred it. If you think it's necessary, you can add touches of glue or a few screws to keep it from sliding, but I don't think it's necessary.
As for attaching toys, you can simply attach premade toys or drill holes through the carpet wherever you want, stick a dowel rod in, and hang a string and toy from the end. It's up to you.
I think you can build a quality cat tree fairly cheaply. If you already have the tools, then you'll just need to buy a 4"x4", a 2"x4", a box of screws, maybe some lag bolts, one L-bracket per arm, a little rope, and find some free carpet. Good luck. Sorry for the long post. It kinda got out of hand.
