AVR UART synchronization problem
Your intuition is correct -- UART hardware doesn't have any synchronization beyond the byte level. (It does synchronize at the byte level for you, via a special start bit as discussed here)

To synchronize "packets" longer than a byte, most high-level serial communication protocols have a special "preamble" of bytes that is guaranteed not to appear in the message. Then there are various strategies to signal the end of a packet: some protocols indicate the end of the message with a special "stop" sequence of bytes that is not allowed to appear in the message. Others use a fixed-length message header that states the precise length of the message.

I haven't used the NMEA protocol personally, but based on this guide it looks like they use '$' as a special character that signals the start of a packet. Is not allowed to appear inside the packet.

So, to receive this data in your program, I think you need to do something like this:


Ignore all bytes until you see a '$'
Then, record each byte to an array, starting from position 0. (Ensure your array is long enough to hold the longest possible valid message. If data exceeds your array length, go back to step 1.).
Stop when you see 'CR' followed by 'LF' (this seems to signal the end of the NMEA packet)
Calculate the checksum, and verify that it matches the transmitted checksum. If not, go back to step 1.
Use the data from your array
Go back to step 1.


This discussion has a lot of good links:
https://stackoverflow.com/questions/1445387/how-do-you-design-a-serial-command-protocol-for-an-embedded-system