A quick search on Google brings up lots of pages like "The Penguins FAQ" stating it is just a myth:
I heard that when Adelie penguins are choosing a mate the male searches for the perfect pebble and presents it to the one he wants as his mate.
It's a myth based on the fact that Adelie penguins build nests out of pebbles. And they build the nest while they do the courting, so it's actually partly true. I guess a penguin who doesn't bring any pebble wouldn't stand a chance, but any pebble will do and both mates bring them in!
I could not find any specific peer reviewed study on this, aside from a couple of papers showing that (very unsurprisingly) hormonal levels play an important role in courtship and nest leaving in Adélie penguins.
Sex steroid and corticosterone levels of Adélie penguins (Pygoscelis adeliae) during courtship and incubation. - Gen Comp Endocrinol., 1999
Should I stay or should I go? Hormonal control of nest abandonment in a long-lived bird, the Adélie penguin. - Horm Behav., 2010
Seaword.org gives a few clues (with refs) about courtship
a. Courtship varies among the species. It generally begins with both
visual and auditory displays. In many species, males display first to
establish a nest site and then to attract a mate.
b. Most penguin species are monogamous (one male breeds with one
female during a mating season) (del Hoyo, et al., 1992); however,
research has shown that some females may have one to three partners in
one season and some males may have one or two partners (Davis and
c. Mate selection is up to the female, and it is the females that
compete for the males (Davis and Speirs, 1990).
d. A female usually selects the same male from the preceding season
(Sparks and Soper, 1987). Adélie penguins have been documented
re-pairing with the previous year's mate 62% of the time. Chinstraps
re-paired in 82% of possible cases, and gentoos re-paired 90% of the
time (Trivelpiece, 1990). In one study of Adélies, females paired with
males within minutes of arriving at the colony (Davis and Speirs,
e. When a female selects a different mate it is usually because her
mate from the previous season fails to return to the nesting area.
Another reason may be mistiming in returning to the nesting area. If
they arrive at different times and miss each other, one or the other
penguin may obtain a new mate (Davis and Speirs, 1990).
Again, the idea that the male builds a pebble nest first and then starts the courtship fits in very well and Occam's razor would favour this one rather than some forced antropomorphisation of penguins.
According to the same page:
One medium-sized gentoo nest was composed of 1,700 pebbles and 70 molled tail feathers (del Hoyo, et al., 1992).
So, it seems the male would have to go on and on bugging the female a couple of thousand times to show her yet another pebble he collected...
This seems unrealistic and this behaviour seems not to have been reported.
We can conclude that, lacking further scientific proof, this is just another myth.