When talking about a structure for holding cars, such as a lot, you park in. "I parked in the lot." "I parked in the parking garage."
You can also talk about parking on a surface or on a street/road. "I parked on the concrete". "I parked on 4th Avenue." "Parking on grass is not good for your car."
In this sense, saying you parked "on the lot" is also acceptable (but not as common) because the lot is a surface. You never park on a parking garage or other fixed structure that your goes goes inside of.
You can also park at a location or destination. "I parked at the store." In this case, the store is your destination. This is a more colloquial way of saying "I parked in the store's parking lot."
In the same sense, you could say you parked at a lot or a garage, since they are also locations. "I parked at the lot on 5th Street." sounds natural. The lot on 5th Street is a location that you parked at.
This can get even more complicated: If you parked in a parking garage located on 6th Street, you could say "I parked on 6th Street" and then clarify with "in the parking garage."
In some cases, all of these are interchangeable. If a friend asks, "where did you park?", you could say "At the lot on 5th Ave" OR "On the lot on 5th Ave" OR "In the lot on 5th Ave". Any of these works because in this situation, the lot could be considered either a location or a surface/structure for cars.