Does anyone know if the new expansion continues the core set's story like of LotR LCG does? Or do we start over with fresh characters/decks?

You're supposed to start fresh, though there are allowances for continuing with the same Investigators and decks. It's a separate storyline but there's no reason they can't be linked.

It starts a new campaign. As for using fresh characters/decks, that is the intention, but you can look towards the end of the core set campaign book for some alternative ideas.

Thank you!!