Bikes on trains are fine outside of the rush hour, you're not allowed to take them during rush hour (I think before 9 and between 4.30 and 6). You need to buy a ticket, which costs six euros per bike and can be used on multiple journeys within one day.
I'd recommend the Utrechtse Heuvelrug and the Veluwe as great places in central Netherlands to visit, as they're not quite as flat as the parts to the east of Utrecht. The cycle path up the north sea coast between Hoek van Holland and Haarlem is also superb. Follow green LF routes wherever possible, these take you the scenic way. See http://routeplanner.fietsersbond.nl/.
The islands are really fantastic too. The central part of the triangle between Amsterdam, Utrecht and Den Haag can be a little dull, there are some pretty villages but you can spend hours cycling across one windy polder without the scenery changing at all.
Hotels are not particularly cheap, Stayokay hostels are usually family oriented and could be a cheaper option. Camping is good, Dutch people like to plan in advance so bigger campsites will expect reservations.
Finally, bike theft is a really big deal in the Netherlands, so make sure you have a proper lock (or two) for your bikes and ideally lock to something.