It's apparently way more legal than I realized: https://en.wikipedia.org/wiki/Topfreedom_in_the_United_State... (potentially NFSW)
The specific things that makes it a crime would be intent to "cause distress, alarm or outrage", or if you are "outraging public decency".
And so e.g. a nudist beach generally does not need any particular permissions on the basis that merely signing it properly, or the place being generally known to be somewhere where people are naked makes it hard to argue it causes distress, alarm or outrage to come across someone naked there.
Of course where exactly the line goes on that is constantly changing and tricky to judge.
E.g. someone stood naked on a plint in Trafalgar Square in the middle of London and police refused to order him to cover up [1] but another naked man on the plint was told to cover up another time.