They took the original negatives and scanned them in at HD, then updated the special effects. They look awesome on blu-ray, and you can toggle between original & new effects while watching. I'm still on season 1, will pick up season 2 when I'm done.
If I recall correctly, the behind-the-scenes video mentioned that there were only 17 shots of the Enterprise that were reused for the 3 years. For the new shots they sometimes show it just like the original shot and other times they showed things that were only mentioned on screen, like other ships alongside the Enterprise or the deploying of the satellites in Operation  Annihilate!.
Unlike Star Wars (Han shot first!), the remastered Star Trek has been well accepted by the fans.