This story seems to have been popularized by S. Venetsky in an unsourced article which first appeared in July 1969 in the Russian journal Metallurgist. The article was reprinted in Tales about Metals (1981). Unfortunately, in neither case does the author cite a source. According to Venetsky, Napoleon III
loved to show off and one day he gave a banquet at which the members
of the royal family and the more illustrious guests were given the
honour of eating with aluminium spoons and forks. The less honourable
ones had to do with the common (at the emperor's table) gold and
silver sets....even the emperor could not provide every guest with the
Venetsky says this happened before 1855, which makes his story plausible at least. Before 1855, aluminium could only be produced in very small quantities and was more expensive than gold. This quickly changed after 1855 when a new process made it much easier to produce; by 1859, aluminium was only worth slightly more than silver.
Aluminium cutlery certainly existed; it is mentioned by Henri Sainte-Claire Deville in his 1859 book De l'aluminium: Ses propiétés, sa fabrication et ses applications. Deville was a French chemist who was given financial assistance by Napoleon III who had a keen interest in aluminium for his army:
It is said that the Emperor's interest in aluminium, in 1854, was
aroused partly by the idea that if it could be had cheaply it would
wonderfully lighten the weight of military equipments, such as spurs,
buttons, sword-handles, sabre-sheaths, helmets, and the imperial
The above source, Aluminium; its history, occurrence, properties, metallurgy and applications, including its alloys (1890) also mentions jewelry and the first aluminium toy (a rattle) made for the emperor's son (but not the cutlery story mentioned by Venetsky). Deville also mentions jewelry but makes no mention of Napoleon III possessing aluminium cutlery.
Other sources would seem to indicate that the timeline doesn't quite fit, that items were not made from aluminium until after 1855 (when aluminium became less valuable than gold, though SJuan's comment on novelty value deserves a mention), and that the first items made were medals. Also, I've yet to find an academic biography of Napoleon III which mentions Venetsky's story.
One of the earliest surviving aluminium objects is this 1857 coin. There are no known surviving pieces of Napoleon III's cutlery, though. Image source: Essai en aluminium de 20 francs or Napoléon III, tête nue 1857 F.531/12 va
There are a number of other, similar, stories doing the rounds online, mostly less plausible than Venetsky's version (see here for example). This French article mentions dishes rather than cutlery, but admits to not being able to find firm evidence.
There is also a highly implausible story concerning the King of Siam - implausible because the first King of Siam to visit France was King Chulalongkorn (Rama V) in 1897. This visit may have been confused with King Mongkut (Rama IV) sending an emissary in 1861, but by this time aluminium was of no greater value than silver. Still, aluminium cutlery could have been used for its novelty value.