First Timer in Europe

Have you bought airline tickets yet? Where are you flying from? How many nights will you spend in Europe, not days?
Would be best to fly into Paris and out of Amsterdam, or vice versa. Saves a lot of time as well as the cost of return ticket between to two.

I did buy airline tickets. It was a really good deal to fly from SLC, Utah to AMS nonstop roundtrip so I booked the tickets. I looked at flying into AMS, and flying out of Paris but it was much more expensive. I've looked at the Thalys prices and it seems like a good deal.

We'll be flying in Oct 5, and will land in AMS Oct 6 in the morning. We fly out on Oct 12 in the morning. So we have 6 nights.

Good advice from Sam regarding the benefits of booking open jaw. Failing that I'd resist the urge to include Paris on this particular trip - would eat up 2 of your days in transit, and that time can be better spent in and around Amsterdam. The train system is cheap and efficient for quick side trips to see the windmills at Zaanse Schans, the pretty university town of Leiden, and a little further afield as well.
Renting bikes for a day and exploring the Waterland area north of the river would make for a pleasant outing...and a great memory for your honeymoon.
Check your local library for guidebooks and select one whose format most appeals to you. Can usually find used copies for just a few dollars on Amazon.
And take a look at the "things to do" pull down menu on TripAdvisor to get an idea of the various attractions in the city and in the area to see what most appeals to you.
There's plenty to keep you busy for 6 days in Amsterdam.

Wow! Nice price!
Suggest spending 3 nights in Central Amsterdam
10/9 take early (7:17 am) Thalys to Paris, hotel for 2 nights. Drop your bags at your hotel then tour Paris for the day, Return to your hotel late afternoon and check in to your room, then out for dinner and evening activities.
10/10 tour Paris for the day.
10/11 check out, again, you should be able to leave your bags at the hotel. Tour Paris until late afternoon then pick up your bags at the hotel and head to Gare du Nord for the 7:25 pm Thalys to Schipol. Get an airport hotel and you're at the airport for your flight home in the morning of 10/12.

As for as what to do in Amsterdam and Paris, get guide books and see what trips your collective triggers. Google local news sources to find out what events are going on as to night life while you are there.
You should buy Thalys tickets now as cheap tickets are already selling out. 2nd class is perfectly fine as it is only about a 3 hour ride.

There is so much to see in and around Amsterdam, I'd suggest staying put and relax into this one destination. The Netherlands is a beautiful country!

Thanks, Sam!!

That sounds like something I was leaning towards schedule wise. I know we are very limited on our time and our work schedules conflict so we don't get to travel often and want to make the most of our time. This will be my fiancé's first time out of the USA too!

What do you suggest as means to getting around the city while in Amsterdam? Would it be too cold to walk/bike around the city during October?

Not too cold, but it could be rainy. You can also get a 72 hour transport pass for 17 EUR per person. That will get you unlimited tram rides. There is a single subway line, but not very useful for tourists as it only has 3 stops in the city center and then its in the 'burbs. Buy in the tourist office outside Centraal station after you arrive there. Train from the airport is 4.20 EUR.

Paris, you can buy a book 10 Metro tickets for 14.20 EUR or 1.90 EUR for a single ride. You can buy the 10-book, called a Carnet on the Thalys train for a slight markup, but it saves a lot of time when you arrive as there are tons of people arriving at Gare du Nord constantly and the ticket machines can get big lines.

want to make the most of our time

There are several takes on that sentence. It could say "see several large cities, even if it means little time for each of them". It could also say "spend as much of our valuable vacation time actually vacationing rather than traveling".

It's your vacation, and only you know what you and your fiancé are going to enjoy most.

Therefore: Yes, it is possible to go to Paris for two days. Yes, you are going to spend a large portion of your vacation time on pure travel: 4 hrs for the train ride alone, + getting to the station/ to the hotel, packing, unpacking - probably closer to a 6 hrs total each way.

So you'll have to decide if that's worth it for you.

Weather-wise it's hard to predict what you are going to get. There definitely always is a chance of rain, so be prepared for that. Near the coast, it can also get quite windy, and we do get a few storms in this part of Europe during fall.

That said, October can be quite beautiful if you are lucky, with golden fall foliage on the trees. If you do decide to spend your time in Amsterdam, maybe you can actually do some exploring by bike and enjoy some beautiful golden fall days. If you like to take pictures, look for the golden light of the low setting sun plus the golden foliage.

Temperatures in October can range anywhere from 0°C to 20°C. Amsterdam, being near the coast, has a moderate climate without great temperature extremes.

Start by getting Rick Steves Amsterdam & the Netherlands (new edition just released May 2017). This not only has all the information you need about getting around, recommended "top sights," etc, but also has tons of day trips and overnights, from cities to small towns and more rural areas, as well as goof-proof directions on how to get there.

As several people have already said, what you "must" see and do is up to you.

A warning: the days will be somewhat short, and the weather is likely to be grey a lot of the time. As long as you're prepared, you'll be fine. Just realize that the pictures and videos you've seen of the city were most likely taken during the spring and summer; Amsterdam won't look like that in October.