You can't prevent the cookies from getting submitted over HTTP the first time, but you can take steps to minimize the damage that could be done by this. The basic principle is that you never, ever honor anything submitted over HTTP, and whenever you receive sensitive information in cleartext, you treat that information as compromised.
Set up your site to redirect from HTTP to HTTPS, and start sending Strict-Transport-Security headers. (You don't have to go for preload until you're good and ready; what I'm about to say will work regardless.)
Then, whenever you see cookies submitted over cleartext HTTP, invalidate all of those cookies on the server side. Don't try to kick them out of the browser's cookie jar at this point, because it isn't guaranteed to work for several reasons (a cleartext HTTP response can't manipulate cookies tagged Secure, older browsers might ignore max-age=0, the man-in-the-middle might strip Set-Cookie altogether in order to keep the victim using the compromised cookie). But don't honor them when they appear in a subsequent HTTPS request. At that point (i.e. only when you have a secure channel established), issue a new session token and require the user to log in again.
Similarly, if you see your login form being submitted in cleartext, don't just invalidate the session cookie, lock the account. Don't redirect the account recovery, login, or registration form from HTTP to HTTPS; instead, issue an error message, instructing the human to fix the URL by hand (it's like a captcha, but it's for bypassing URL rewriting in sslstrip ;-). And any page that should be accessible only to logged-in users should redirect to the front page, not to HTTPS-itself, when accessed via cleartext.
In addition, make sure that your session cookies are both unforgeable and meaningless. Most Web frameworks will do this for you automatically nowadays, but if you haven't got one, the simplest construction that will work is: each session cookie is a large (64 bits might be enough, 128 is definitely enough) random number, generated by a cryptographically secure RNG, plus a message authentication code signing that number. You can use a symmetric MAC for this, because the cookie only needs to be authenticated by the site, which is the same entity that issued the MAC, so it will know the same secret both times. If a cookie comes in with an invalid MAC, ignore it, regardless of how you got it -- pretend you never got it at all. (This even supersedes the rule about invalidating cookies that come in over HTTP. You don't want the attacker to be able to force-logout people by forging requests.) But if the MAC is valid, then you use the random number as the key to a database table recording all of the actual information associated with a user session.
It is also best practice not to issue any cookies at all until someone tries to log in. That makes it much harder for a MITM to get their hands on a valid cookie, and it also makes it easier for you to comply with GDPR.
After reading the discussion on the other answers, I now realize OP is concerned with a very particular scenario: a new user to the site accesses it for the very first time through a man-in-the-middle, who is terminating HTTPS, stripping out HSTS and rewriting all links, and relaying the site unencrypted to the hypothetical new user. Against this, indeed, the only thing that can possibly help is HSTS preload. In the absence of HSTS preload, the new user's account will be "born compromised", as it were, and the attacker will know everything about it: not just the session cookie, but the username and password, and the email address used for account recovery, and every bit of personal information that the victim entered. This is nasty and, alas, more plausible than you might think.
But if you get just one chance to interact with the user over a channel that isn't being actively tampered with, you can push HSTS and secure session cookies and all the advice above will be useful.