The Cart's estimate shipping is really just an estimate tool.
If the user is already logged in and has a valid profile, it will autopopulate into the Checkout address fields allowing the available shipping methods to show. Otherwise, if not logged in, the address fields on the Checkout page are essentially blank and since the addresses are blank, we cannot determine what shipping methods are available. It would be nice in the future to remember the address entered (country, state, city, zip code) in the Cart estimate tool and use that information to populate into the Checkout address fields so that the selected shipping method is preserved. We'll add a note into our todo list to consider improving.
Thank you.