Cortana is a shipboard AI (articificial intelligence) from the human craft Pillar of Autumn. Apparently the Covenant are after her, and it's your job to stop them from getting their hands on her.

Early in Halo's development and long before its announcement, several emails were sent from computers at Bungie under the name Cortana that elicit connections the Marathon universe and possibly AIs from that story, perhaps Durandal.

According to those emails sent to Marathon's Story she currently resides in (yes, in) a hybrid war machine, presumably a cyborg. The cyborg's feelings on this are unknown. She is almost certainly going to be a major part of the storyline.

More on the letters can be found in the Halo article The Cortana Letters.

The penultimate weekly Halo Update contained a screenshot of Cortana.