In the HTTP protocol, the browser sends a request and the server sends an answer. If the answer includes a virtual include like <!--#exec cgi="/cgi-bin/myscript.cgi" -->, the server may act on that to execute the CGI and incorporate the result, but the simplest implementation will grab only the text output, and ignore meta-information sent from that CGI output such as new cookies - chances are, the server already thinks it knows what the header to return to the browser (cookies and all) should look like.

If there is a straightforward way for your primary CGI to determine that the cookie will be required and send it directly, I'd suggest taking that approach. I don't know of any simple alternative.