Power Berries in Harvest Moon 64 are red fruits you find through doing different things. Some are easy to get, while some are more challenging. They are very valuable, and eating them will increase your stamina. There are a total of 10 in the game.
During the Winter season, smash the boulder on the frozen pond near the Fisherman's tent with your Golden Hammer.
Till your land as much as possible, eventually you will find one. There is no trick to this one; it's just a matter of luck.
If you are lucky, you will find one digging in the Mine during the Winter.
While you have full strength, throw an egg or vegetable into the Goddess Pond and wish for strength.
Go fishing off of the dock at the beach. Eventually, you will catch a Power Berry.
Throw a Large Fish into the pond by the Fisherman's tent some time between 9:00 and 5:00, and the Kappa will give a Berry in return.
Give a marble to the Harvest Sprites. To get a marble, grow a minimum of 16 Pink Cat Mint Flowers (i.e. just under 2 full 3 x 3 flower beds. When all of the flowers are fully grown, Stu will come and ask for one. He doesn't have money, but he trades you the marble for a flower.
Become friends with Basil, and he will give you one when he returns in the Spring.