I also use black blasting sand in my tank. $8 for a 50lb bag. Or if you want a more natural look you can buy pea gravel for $3 for a 50 lb bag. I've gotten all four of my tanks from craigslist with a crapload of accessories for under $250. I have a 75, 29, 20, and 10 gallon - all of them came with a heater, filter, light, and lid. Some came with gravel and decorations too. The 20 came with a stand. I built a stand out of 2x4 lumber for the 75. I use poly fill from the craft store for filter media.
One idea I came up with all on my own was to use baby food as a treat for my fish. I buy baby food made out of peas, freeze it into a sheet shape, and once it's frozen I cut it into cubes. It does make my water a bit cloudy temporarily though.
For plants, if you have any friends with planted tanks, you could ask them if they're ok with splitting some of their plants and giving them to you. Then you get free live plants.