I have done both, and actually depending on how you do things, a paludarium can be cheaper. You can get pretty inventive when it comes to building materials.
Some of the ways to cut corners:
-Buying pea gravel at Lowe's or Home Depot (~$3.00 for 50 lbs.)
(also works for aquariums, just rinse thoroughly to remove foreign materials)
-Buying plants at Lowe's or even from places like Peace of the Tropics isn't too bad. A $5 pothos plant while not the prettiest, works fine and goes a long way. Always rinse plants thoroughly to remove any fertilizer.
-As far a lighting goes, I have never spent big money on fancy lights and my plants grow just fine, including orchids and bromeliads. A local reptile show should have plenty of cheap used aquarium light fixtures. I have also used cheap "Grow Lights" from Wlamart which hold 2 24" flourescent lights.
-Potting mixes can be done pretty cheaply as well. I have made my own using various mixtures, but I usually start with Eco-Earth coconut fiber bedding which is reasonably cheap and comes in expandable bicks.
-For decor, I have used sterilized rocks that I gathered from a creek on my farm as well as live moss that grows on my farm. Even cheaper yet is leaf litter which is free.
Of course I have saved all of my aquarium supplies and old aquariums which also helps cut costs, but you can do a 20-40 gallon paludarium to start and go from there. EVeryone has their own preferences and through trial and error have found out what works for them. I would look at several pictures of different terrarium designs and also think about what kind of herps you want to keep before building anything.
My dream paluadrium would be a 75 bowfron with rock cliffs containing brackish fish and mudskippers. There used to a tank like that at the store where I worked and watching the mudskippers "fight" all day was very entertaining.