The Stellazzio side quest involves collecting Stellazzios from around the world and returning them to Queen Stella. She will provide you with a reward for each one that you return to her.
Queen Stella can be found in Treno near the Synthesis Shop as shown in the screenshots above. The locations of each of the Stellazzio coins is listed below along with a list of rewards that you will receive for turning them in.
Examine the fountain at the entrance of Treno and choose to “Throw in 10 gil”. The Stellazzio will appear after doing this 13 times.
Search the area behind the Item Shop stall in Treno (shown in the screenshot).
Located in Alexandria Castle near the huge Neptune Statue that also doubles as a transit vehicle to the docks.
Can be found in the Business District on the left side of the main plaza of Lindblum (where the pickles were sold).
This last Stellazzio can be found in the exact same place that Scorpio was located in Quan's Dwelling and only appears after you have obtained and turned in all of the other Stellazzios.
The rewards that you receive are based on how many Stellazzios you have turned in and do not change depending on which specific Stellazzio you have. They are as follows: