Beginner Tips

Starting location:

Near water: With no infinite water, until you get a Railcraft Water Tank, you will be making frequent trips to fetch water.
Near sand: You will need sand for many of the early multiblock recipes, and for glass.
Near exposed minerals: This is difficult in GTNH since ores spawn in veins. Sometimes you might get lucky and find a vein on the surface, but it's pretty unlikely. Always mark any you find.
Near a lava pool: Handy for refilling your smeltery.
Villages: A great place to setup a base. Villages however should be avoided until you have a bed, otherwise the villagers will be slaughtered while you hole up at night. Steal a door - you won't get one until you smelt iron.
Roguelike Dungeons: The large brick buildings on the surface, with a bed and furnace, perfect for starting a base. The stairs down can be blocked off to prevent monsters from coming up. Also, the bricks can be cannibalized later for multiblock structures. You can cheese the dungeon by going down with only torches and lighting it all up before returning for loot.

I suggest looking for a location relatively flat, near sand, with good access to a body of water. Minerals will have to be searched for no matter what, and with a relatively flat location it makes it easier to get around. If possible, be relatively near an oil spout - ~128 blocks. If you are closer, cover the spout with dirt/cobble roof. Lightning or infernal mobs can set it on fire.

Transportation

Horses are actually very useful early/mid game. Find or craft a saddle and lead per the quest in Transportation. If you can, craft a Golden Lasso as well - horses don't do well crossing water.

Make paths going the cardinal directions from your base. Smooth them as much as possible, and use stairs to go up/down.

Exploration

In early game, you should have at least the surface 256 blocks around you explored. Once you get a horse, explore further out. After you get steel, you can make a hang-glider and explore thousands of blocks away from base.

Keep an eye on the sun! It gets really dark, really fast. If you don't have a bed, you'll have to shiver in a hole until daybreak.

Watch out for blood moons! If this occurs, you cannot sleep through the night. If the torches in your area start looking reddish, IMMEDIATELY stop and build an emergency fort.

Locations to note

Villages - scavenge for useful materials, Witchery books, smeltery blocks. Note any interesting trades for later.
Stonehenges - These can have chests or droppers with good loot.
Obsidian totems - 1x1 spire of obsidian - avoid these. May be surrounded by difficult to kill mobs.
Aluminum Gravel - Always gather any you see. Aluminum veins cannot be found in the Overworld.
Rubber trees - Gather until you have ~16+ saplings. Keep the wood too for centrifuging later. Frequent around rivers. Look for trees that have a 3 leaf tall spire at the top.
Vanilla clay - Rivers and lakebeds have clay - gather all/as much as you can. To make mining less frustrating, make a cobblestone wall around the outside of the clay patch, and fill in the water with sand/gravel. Then mine it all out. Othewise mining underwater can be pretty frustrating since no infinite water means the water drains, pushing you around.
Gravel - Initially you will need gravel for flint tools, but once you start mining you'll have plenty from that.
Mountains - Look for mountains with stained clay - good source for mass quantities of clay dust instead of vanilla clay
Silverwood trees - Very rare, may need to travel several thousand blocks to find them. They have a distinctive blue color. Look for Cherry groves or Sacred Springs.
Slime islands - Mark for later - Not super common but there should be at least a couple with ~2000 blocks of you.
Roguelike Dungeons - Explore the surface levels and mark for later. Easier to cannibalize the bricks than making your own.
Pam's gardens - Don't break them, gather them instead. You can plant them back at your base and they will spread. Once you 3-4, then you can break excess.
Meteors - Gather all the stone, save it for later. Ok for building since it has good blast resistance. The center will have a Sky Stone chest which is also blast resistant. Keep the contents for later.
Red/Black granite - Ok for building since it has good blast resistance. Black granite can be difficult to see.
Snow - Gather a few stacks if you can find some. Good for smoothies/Delighted meals later.

GT:NH specifics

The smeltery does not produce aluminum ingots, but it can create aluminum brass alloy for making molds.