That's very weird. I've had it on my phone since the very first iOS 16 Beta, it was quite literally a day 1 feature.
I do know that the weather lock screen widget needs constant location access (for obvious reasons). The only reason I can think that you aren't seeing it is because your Weather app is totally restricted from using you location unless you open the app.