Ive seen topics where if you remove a mod you should start over. Same apply if you add a mod. I just started a new game and i saw a mod that i liked.

What does the readme say for that mod you like?

Most mods you can add to an ongoing game. If they require or suggest a new game, then the Readme will state that.

What you want to do with any mod is fork your save so you can remove the mod and go back to a save slot from before you added the mod to the game. Even better is to have a Test Save that you made with no mods on the game to load to test a mod with. This way you won't introduce issues into your characters that you care about. The non modded test save will tell you if you have issues with the mod mix, where a save from a modded game might have issues with the new mod mix. This way you know what the root issue is.

Depends on the mod and what the mod does.

Like it was stated earlier check the mods descriptions or readme. That should tell if it is suggested to be on a fresh new game. I believe some mods might be dependent on how far the game is progressed or that it has to be installed before a certain quest is done. Again check the mods readme.

If a mod does significant changes to game mechanics, balance, etc., then it's necessary to start a new game. I'd consider mods like SkyRe to go into this category.

Fortunately vast majority of mods can be added to existing save without a major hassle as said already. Some mods might require cell reset to start functioning properly. Just read the installation instructions of each mod.

If you just started a new game, that's the best time to try the new mod, before you invest too much time into a character if you like or don't like it.