What does this phrase mean? I think of maybe something is going to be really famous in the future, but now it's just not so popular. And it's on its way out. Is that correct?
No, it's actually kind of backwards from what you suggest, but you are right that it has to do with fame or popularity of something.
Specifically, the phrase is a reference to trends. When something is "trending down" or "losing popularity," it is said to be "on its way out." If it is a product, maybe it is still available in stores, but it isn't the most popular or talked about item and is losing momentum against some new trend.