J.K. Rowling has never exactly laid out what parts of Half-Blood Prince she cut from Chamber of Secrets, but, if I recall correctly, the story about Snape being the half-blood prince was originally slated for Chamber of Secrets.
J.K. Rowling: There is no trace of the HBP storyline left in CoS, rather the link between the two books relates to a discovery Harry made in CoS that foreshadows something he finds out in HBP. Harry Potter and the Half Blood Prince was once, in the long distant past, a possibility for Chamber of Secrets, and from that we deduced that it was genuine. Certain crucial pieces of information in book six were originally planned for Chamber of Secrets, but very early on (first draft of CoS) I realised that this information's proper home was book six. I have said before now that CoS holds some very important clues to the ultimate end of the series. Not as many as six, obviously, but there is a link.
J.K. Rowling - ACCIO QUOTE
I guess this to be referring to Horcruxes. She says the information in question would have been presented too early in CoS; Horcruxes makes sense in this regard. If Harry hadn't learned of the prophecy until OOTP, I might have wondered if the issue in question was that Snape had been the one to take the info from the prophecy to Voldemort. Harry didn't find out it was Snape until HBP. All in all, though, the concept of Horcruxes makes the most sense to me.