It appears that Bungie wanted his model to load before the cutscene he later appears in; they thus coded him with scripts to load early in the level, and used the area outside of the level as a storage area. Technically, this makes him not an Easter egg, although it is fun to find him. He can be shot and killed, just like any other Marine.
To find him, the player must stay inside the Pelican that drops you off at the beginning of the level. To do this, start throwing grenades as soon as the player is able to. Stay inside the dropship as it flies off. After it travels a certain distance, the Pelican will drop the player off outside of the level barriers. By exploring around, the player will eventually come across the Marine.
The Hidden Marine on 343 Guilty Spark in Halo: Combat Evolved Anniversary