I have taken the bus from Fredericton, NB to Halifax, NS at least 10 times and take the train Montreal-Halifax three times. If you have a choice I would avoid both of these options.
For the most part you won't see too much on either method of transport. The train usually runs straight through the forest. The bus runs along either the highway or some rural roads. Nothing too pretty on either method of transport.
The train will be about the same price as flying if you have a single seat (not a berth or cabin). This is comfortable for a day trip but for the ~20 hour trip from Montreal-Halifax this is very uncomfortable. The train is always late as well. On my 3 trips the train has been as little as two hours late to as much as 6 hours late.
The bus ride is very long. Halifax-Fredericton is about 7.5hours by bus or 4.5 hours by car. I spoke to someone who did Halifax-Montreal by bus and they mentioned that it was 25+ hours.
If I was going to Nova Scotia I would probably drive. You can be in Halifax in a day of driving (16 hours) or you can do it it two shorter drives. Halifax offers a wealth of things to do in the city but you will undoubtedly want to see some of the smaller touristic areas that are harder to access without a car.
Driving will probably also be cheaper than bus/train but also gives you some other money saving opportunities. Depending on the time you of year you could stay in camp grounds instead of hotels. This can save $75/day.