Cool potato salad is one of the great summer dishes, though I can eat it on any day of the year. Every culture that eats potatoes probably has its own unique recipe for potato salad. While potatoes are not really part of traditional Japanese cuisine, it's now a fixture in everyday cooking. When I was in junior high in the suburbs of Tokyo, our school's sandwich concession even had something called a 'vegetable sandwich', which was actually a mound of potato salad between two slices of white bread. Potato salad is often tucked into a corner of an obento box (lunch box), and it's also a popular beer or sake snack. My ideal Japanese-theme picnic would include onigiri (rice balls) , some chicken karaage , and potato salad for sure.
Japanese potato salad has a mild, creamy flavor, with no acidic undertone; unlike American or German style potato salads, no vinegar is used. It's seasoned only with salt and a little pepper, and lots and lots of mayonnaise, and is just a bit sweet from the other vegetables mixed in - boiled carrots, thinly sliced cucumber, and onion. Some people even add a little sugar. Chopped boiled egg adds to the richness. It's really designed to go well with rice (as are most Japanese savory dishes).
The ideal mayo to use is a Japanese one of course; Kewpie Mayonnaise  is classic, but there are other (and some say, better) brands too. Look for them at your local Japanese or Asian grocery store. If you make your own , use a flavor-neutral vegetable oil such as canola or safflower, not extra virgin olive oil. ("Extra Light" olive oil is fine.) Lacking access to Japanese mayonnaise or the time to make your own though, any commercial mayo will do as long as it's not too heavy on the vinegar flavor. Salad cream should not be used however.
Boil the potatoes in their skins until tender (you can poke a skewer through one without any resistance). Boil the carrot, unpeeled, in the same pot. Boil the egg until hard boiled at the same time.
In the meantime, slice the cucumber and the onion very thinly. Sprinkle both with a little salt, and let sit for a while (10 minutes or more) until the vegetables exude their juices. Squeeze firmly to get rid of the juices.
When the potatoes and carrot are done, drain peel them while still hot (holding each in a kitchen towel to peel them helps). Cut the potatoes into small pieces, and slice the carrot. Toss with a little salt and pepper and leave to cool.
Peel the hard boiled egg and chop up finely.
When the potatoes and carrot mixture has cooled to room temperature, mix in the cucumber, onion and egg. Mix in the mayonnaise. Cover with plastic wrap and cool in the refrigerator until serving time (ideally at least one hour).
If you are bringing this to a picnic be sure to pack it in a cooler - it will keep better, and taste better chilled than at room temperature. If you are packing it in an obento box, make sure the rice and other ingredients have cooled before tucking in the salad, or carry the salad in a separate container.
[Update:] A not-traditional but still tasty vegan version  of this potato salad.