We went to Europe last summer with our US passports and got a stamp upon entry in Paris. We came back home to the US on a cruise from Italy and have no exit stamps whatsoever. Im wondering how anyone would know that we actually left within the 90 days allowed. Will we have any problems when we go back this summer?
There are no Schengen-wide records of entries and exits so no way for border guards to check how long you have stayed in Europe beyond examining the stamps in your passport.
Furthermore, the Schengen border code explicitly puts the onus of proving you haven't stayed longer than 90 days on you:
Presumption as regards fulfilment of conditions of duration of stay
If the travel document of a third-country national does not bear an entry stamp, the competent national authorities may presume that the holder does not fulfil, or no longer fulfils, the conditions of duration of stay applicable within the Member State concerned.
The presumption referred to in paragraph 1 may be rebutted where the third-country national provides, by any means, credible evidence, such as transport tickets or proof of his or her presence outside the territory of the Member States, that he or she has respected the conditions relating to the duration of a short stay.
- The relevant provisions of paragraph 1 and 2 shall apply mutatis mutandis in the absence of an exit stamp.
So in theory, you could indeed run into some trouble for the missing exit stamp. Taking any documents pertaining to the cruise with you is therefore definitely a good idea. Even things like credit card charges suggesting you were physically out of the Schengen area at some point before the end of the 90-day period might help.
If border guards do notice the discrepancy and treat it “by the book”, you should then receive a stamp (and possibly a special form) indicating that you proved to their satisfaction that you left the Schengen area in time and when. Of course, it's also possible that nobody will notice or that they do notice but choose to wave you through without bothering with the paperwork.
It's only a problem when it becomes a problem. Canada/USA has a similar issue - no outbound controls and LOTS of cross-border road / foot / marine traffic.
People from first-world countries going to Europe will likely never have an issue. You arrived, took a fairly expensive holiday, and you say you returned when you did. Highly unlikely you hid in the French provinces picking grapes for €50 a day. Your verbal claim of "I returned to the USA on the HMS Lollipop, departing Civitavecchia on April 1, arriving Manhattan April 10" is far too easy to check out and thus it is unlikely you are lying.
Immigration officials process a lot of arrivals daily, and the vast majority are not problems. They will be in trouble themselves if they attempt to make a federal case out of every tiny irregularity as it's a waste of resources.
If you win the random-inspection lottery* all you need to do is provide proof that you were not in Europe after the 90-day limit. Work records, bank transaction like an ATM withdrawl, maybe today they will even take Facebook / Twitter activity.
- best comment ever from a customs inspector: "Nah, your answers were fine. It's random. Personally I think random inspections are a waste of my time so lets go through the motions and get you out of here". 3 formal questions, 3 formal answers, bag x-ray, and he walked me out past the exit line.
As you already pointed out - they don't know for sure if you left within 90 days. However, it is very unlikely going to give you any problems. As recommended by @Willeke, you could bring your former travel documents/itinerary along in case there are any questions.
The 90 days period only applies within a 180 days time frame, which has long expired since last summer and you can enter the Schengen area again for up to 90 days as a tourist.
I don't know how long the cruise was, but you probably have a USA re-entry stamp.