Firstly, I suggest you don't worry about this issue. There is AMPLE room to serialize tons of identifiers to.
Secondly it's not stored by web-server
but by web-domain
-- e.g., www.google.com
and not the 100's of different physical servers that serve the Google domain.
Thirdly if you do have to worry know that their are two possible cookie headers. The sizes of these cookie headers are determined by the browser software limits.
Design Discussion
What you don't want to use the cookie header for is sending details about a client's session. E.g., don't try to stuff the email a client is typing into a cookie if you are building an email front-end. Instead you would send the client a cookie that represents his identity+session: you store all sessions data against this identity. You can store tens of identifiers (4-16 bytes) per cookie header and no one needs more than say 4 of these. The cookies data (as an integer) tends to be encoded to base64 which increases the byte-count.
Performance
Your browser sends a plethora of headers to a web-server. The cookie is just another 100-1000 bytes (mostly closer to 100). At both extremes it takes only a fraction of time to send these to the web-server -- when placed into context of course. You should keep in mind that the web is built on text based protocols.