Would Apple reject a native app because it stores cookies send back and forth to the server?
No. Cookie are the normal way to maintain sessions to a server over HTTP, and there is nothing in the app store rules to forbid them (would be absurd if there were... though admittedly some of the app store rules are weird;-).