At some stage, you're probably going to want to gain access to Professor Palin's spiffy Class 5 thruster modifications. He requires you to travel at least 5000 LY away from the system you started the game at before he'll even start talking to you. So if you're tempted to "give this exploration thing a go" just once, then I'd strongly recommend going at least 5000 LYs out, otherwise you're going to have to do a second 5000 LY trip later when you want access to Palin. A typical explorer can do 1000 LYs a day, so doing the Palin Run isn't going to be a simple one-day job.
Make sure you have a Detailed Surface Scanner installed. The difference in credits earned between a Level 2 Scan (done without the DSS) and a level 3 scan (done with a DSS) can be significant.
To maximize exploration credits, you'll want to try to claim the 50% bonuses for being the first CMDR to scan objects. Unfortunately, since most of the "interesting" objects in the Galaxy within 5000 LY of Sol are thoroughly explored by now and the paths out to them well-travelled, getting out to a region Where No-one Has Gone Before means aiming for nothing. Or, do what I did: aim for a tourist target (mine was the hypergiant star VY Canis Majoris) and then when you get there, aim for another target even further out; the direct A to C line from Sol might be explored, but the B to C line was all mine to claim.
The most valuable things in the universe are (in approximate order of value) black holes, neutron stars, Earth-like planets and large terraformable waterworlds. The most valuable single object in the universe is Sag A, the supermassive black hole in the Galactic Core, worth about 650,000 credits, but it's quite a bit further away than the 5000 LY you need for a Palin Run.
Since you can't see Earth-like planets from the galaxy map but you can see neutron stars and black holes quickly and easily by using the map filters, the quickest, most reliable way to earn cash by Exploration is "neutron field farming". There are certain regions of the galaxy, about halfway between Sol and the Core, where neutron stars are extremely abundant. So even a relatively new player in a cheap explorer like a Hauler, Diamondback or Cobra III can spend a couple of weeks flying out to the neutron fields, spend a week farming, spend another couple weeks flying home, and become instant Elite in Exploration in about a month. Exploration ranking is determined purely by profits earned by selling exploration data and you only need about 150 million credits worth to hit Elite, compared to the 1 billion credits you need to get Elite Trader and the complex calculations and RNG reliance needed to get Elite Combat. It's boring (even a "true explorer" finds neutron farming boring) but it's probably the quickest, safest and most predictable way to attain an Elite ranking in the game.