What are the differences between these two words? Is автострада just the same thing, but less used? Or do they have different meanings?
Шоссе is a paved highway outside of built-up areas or generally any paved road with several lanes outside a city
Автострада is a controlled-access highway that doesn't have single-level interchanges or crossings with other roads.
Moreover, there is also магистраль (автомагистраль) for arterial thoroughfare in urban areas or road that connects two or more urban areas.
Шоссе is a major atrterial road, whether in a city or (more typical) between cities. Equivalent to highway.
Автострада is a slightly dated word (was more popular in the 60-70s) of Italian origin for what is officially known as автомагистраль. Equivalent to freeway or motorway.
That said, colloquially it is common to use шоссе generically for any major road, even if it's formally an автомагистраль. Perhaps because it's a shorter word.