For the stay in Paris I would recommend St Christopher's Paris Hostel
I stayed there during my first trip to Paris. People would tell you that it's not the best area to stay at, but it's not true.
The hostel is good also because you get a discount for the diner and it's really much cheaper than in the other places.
One important thing not to miss in Paris is the roof of Galeries Lafayette. Not everybody knows that you get get upstairs for free and there's a really great view on the whole city. To get there, just go into the store (metro Opera) and go to the last floor. Then there will be a regular stairs that will lead you to the roof.
Moving between the cities can be expensive, so if you want to take a train, book in advance at SNCF site.
If you want to save and don't mind taking a bus, have a look at Eurolines site.
It's really much cheaper, but the schedule is not always as good as a train and you will spend 2-3 time more on the road.