“Your explorers failed to find anyone.”, what I need to find someone

You must assign the hunter job to a kitten in the village tab. That will produce 0.060 catpower per tick. This is the only source of catpower ingame right now.

The lizards are the first trade option you get. It is happening only one time, and you don't have to click anything. This trade route opens after 20 years of in-game time. The other trade routes you have to unlock yourself by sending explorers. So nothing special happened, you just passed the 20 year in-game time.

update:

But, you restarted, so you probably have karma. Then something special is happening:

update: function(){
    if (!this.hasUnlockedRaces()){

        var unlockYear = 20;
        if (this.game.karmaKittens > 0 ){
            unlockYear = 5;
        }

        if (this.game.calendar.year < unlockYear){
            return;
        }

        var race = this.unlockRandomRace();

        this.game.diplomacyTab.visible = true;
        this.game.render();

        this.game.msg("An emissary of " + race.title + " comes to your village", "notice");
    } 
}

The initial race is indeed random (I didn't know, I assumed lizards because it was lizards twice for me), and the unlock year is 5 if you have karma.