So you got a YES on the Badfish test: https://filippo.io/Badfish/
Let's work together to fix that. Important: don't do this if you don't feel comfortable following the instructions, ask for help, these are administrative operations.
Update: Lenovo has a picture-rich guide for Windows 8 (now complete) and an automated Open Source removal tool.
This might or might not be needed, but check to be sure.
Close or quit your web browser(s) completely. You can also restart your computer.
Load https://filippo.io/Badfish again from both Chrome/IE and Firefox, and make sure you get a No this time.
Note: The test might still be stuck on the old result. If after you follow the steps to remove Superfish you still get a YES, visit canibesuperphished.com. If you are warned by your web browser before you can access the site, Superfish has been successfully removed.
Congratulations, you fixed your new laptop! It might be a good idea to change important passwords now. (It's always a good idea anyway.)
Thanks to: LifeHacker, PCWorld, Thewirecutter, @smorewithface.