Easyjet only sells 6 months or so ahead, so the best I could check was for next March, but you could fly Paris to Barcelona pretty much any day for 34.49 pounds each -- so about $300 for all four of you, and it is only a 2 hour flight. If you want to take the train, do it, but do look into flights on intra-European carriers, too. Vueling is another that sells inexpensive one way flights between Paris and Barcelona, but I seem to remember it had fewer flights to choose from than Easyjet, at least last year.
Yes, be sure to plan to get there the day before to be safe (although I will confess that we flew from Paris to Barcelona the morning of our transAtlantic cruise last year, and luckily had no problem).
Julie has a lot of great information posted - the only thing I would add is that with Easyjet and other budget European airlines is to check their baggage allowance as some charge a large fee for additional bags and bags that are over their weight limit. My sister was looking into one of the budget airlines going from Paris to Florence Italy this past summer and when reading the fine print it would have cost her more then a major airline once she figured out all the baggage fees. Just a heads up to read the fine print whomever you decide to go with
One company that I used a few years ago is Europebyair.com and had a very nice flight from Venice to Catania, Sicily