About maybe halfway-ish through the game, when you get to Canalave City, you have to take a boat to Iron Island. There, partway through the cave, you will meet a man named Riley who will travel through part of the cave with you. He will have a Lucario and will heal your pokemon between battles. While you're with him all battles will be double battles, including wild encounters. Once you reach the end of the cave and defeat a couple Galactic grunts, he will give you an egg. That egg will have a Riolu, the pre-evolution to Lucario. It evolves with friendship during the day. You'll have to train it up from level 1, of course, but trust me, it's worth it.