First off, we prefer to use the word "tagged" to describe getting your CMDR name placed next to an object, to avoid confusion with actual star and planet names. Actually renaming stars and planets isn't something that CMDRs can do without help from the Devs.
Now, entire star systems don't get "tagged" all at once. Individual celestial objects do, one at a time - stars, planets, moons etc. To "tag" an object, you first need to find it (with a Discovery Scanner, though "old school" explorers had to use parallax flying) then fly your ship up close enough to it to activate your ship's surface scanner. Once the surface scan finishes, the planet is considered "explored" by your ship's computer and if you're the first player to ever do this to that particular object, then you get your name there as the First Discoverer.
As I said, each object in a star system has a separate "discovered by" tag. It's entirely possible for a dozen different CMDRs to get their names tagged on different objects within the system. This is particularly noticeable inside inhabited space, as these stars were explored very early in the game when many of the helpful scanning aids (such as the Advanced Discovery Scanner) were not yet invented, so they were discovered and tagged piecemeal, one planet at a time.
It's important to note that "Exploring", as described above, still counts towards your Exploration ranking and you still get paid by Universal Catographics when you hand the data in, even if you're not the first person to ever explore that system. Whether you're the second person to explore it or the 100,000th person to explore it, you still get paid the same amount of cash for exploring it. Crazy, but true. UC only pays a bonus for "First Discovered by" data.
It should also be pointed out that you do need to be the first person to actually sell the exploration data at a Universal Cartographics office (every space station has one) for the tag to "count". So theoretically, someone else can beat you to the tag if they scan the same object and make it back to a space station before you do. It's unlikely to happen at random, but if you discover a particularly valuable object (such as an Earth-like planet), it's best not to blab about it's exact location on the open forum until you're safely docked, the data is safely sold and your tag is firmly in place.
A corollary of this is also that if you happen to explode before selling the data, any data you had onboard your ship is lost. So when you go out exploring for a long time and you've got millions of credits worth of data in your ship's computer, be careful when coming home.
So, which systems can you Explore? When you start the game, there are two kinds of star systems on your galactic map: Explored and Unexplored. "Explored" stars are high-population, advanced economies. No-one can ever claim "discovered by" tags for these systems. Their system maps are pre-loaded into your navigation computer, which you can look at by clicking on the System Map icon on the starmap; for Explored systems, this icon will be white, for Unexplored, it will be red and you can't click on it. Unexplored systems are either uninhabited or only have small, low population colonies inside them - though the inhabited ones will still have starports. It may seem odd to call a star system with 500,000 people and a couple of starports "Unexplored", but that's how things are. You can purchase map data for certain frequently visited "Unexplored" systems from the galactic map while you are docked at a starport, or you can fly there and Explore the place yourself.
Finally, it's a safe bet that every single star close to newbie space has been thoroughly Explored and tagged. Every inhabited star system has been visited at least once now, I'm sure - most get visited by somebody at least once a day - and most objects in most systems within the sphere of Human space have been tagged by now. To find a truly Unexplored, untagged system, you need to fly out quite a long way - about 500 LY or more from Sol should do the trick.