Congratulations !

If you are planning on using miles, I would start looking now for your options. Keep in mind that premium cabin (Business, First) may not be released until closer to the date so that is a little bit of a risk.
I find that prices are cheapest about 3 months in advance but again, if you must be there a certain date then you could consider buying it now and make sure you have your specific date.
If you are not worried about collecting miles then start with the "usual suspects" such as orbitz, travelocity, any of the airline sites, kayak, etc..... Keep in mind that some of these fares do not accrue miles and cannot be upgraded.
Not sure where you live but if you live in a small town it may pay to look at farther away airport or even buy separate tickets in order to get a "special deal" out of a larger airport. Again, there are risks involved in this strategy.

If you have good credit, have you considered getting a CHASE credit card with United airlines under your name and a second one under her name; it gives you 50,000 miles just to sign on and it is enough for a round trip flight to Paris from the US. There is a minimum you need to spend in a "short period of time" so look at the details.

As far as where to stay, it depends somewhat on your budget, loyalty to a certain hotel chain, or if you have points in any of the hotel programs. Budget is the main factor; you can get a decent room in a great area for around $200 going with Bestwestern (they actually have very nice standard mid-level hotels in Paris). Some of the better hotels (like the one mentioned in Place Vendome will run $600-800 for a regular room per night and $many thousands for a suite).
Feel free to PM me if you want some very specific advice; general questions are hard to answer and they have already been answered here many times so do a search.