You can use a load balancer that supports sticky sessions, this way users are always routed to the same server.
Your cache would typically live outside of your application instance. For example with Rails you could use Redis as your cache backend and Redis would be running on its own server that's unrelated to your load balancer.
That's typically what people mean when they say they run "stateless" servers. For horizontally scaling most web applications, you want to keep them as dumb as possible. They should be disposable. I would strive for that even if you plan to do a small single server deployment.
I've dealt with some pretty big web apps before. A single SQL database can go a really really really really long ways as long as you avoid silly mistakes like N+1 queries and understand how to profile slow queries on demand. You can also cache expensive queries to avoid hitting your DB entirely.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.