Every so often, you'll get a pop-up that says something to the effect that: Your people are so pleased they want to expand your palace. At that point, you'll be take to the palace screen. Move your cursor around and you'll see the various possible improvements that you can make, Pick one and click. Unfortunately, I don't know what the triggering events for palace expansion are.
I sometimes get the palace expansion screen after a military victory or when a lot of city improvements are constructed in one turn. I also seem to get to expand my palace when many cities are celebrating WLTKD. There are screenshots on these forums that show the palace expansion box pop up during mass rioting and I once got to expand my palace after a barbarian pillaged one of my cities so it could just be random.