The time it takes for the populous to stop thinking in terms of East and West will depend greatly on how different they are to begin with and how different you wish to allow them to remain. For greatest effect, there will have to be both public and hidden efforts toward unification.
Remove Reminders of Historic Us vs Them
My first thought was mentioned by Scimonster. Carve out a neutral district along the border of the two original empires and build a new capitol city there.
Choosing the location may be tricky depending on history.If there was a contested site that both sides associate strongly with, it may be ideal to use it and publicize it as a symbol of the union. On the other hand if any mention of the location just stirs up resentment of past wrongs done by the other side, it is probably not appropriate.
Along with the new capitol, commission new national symbols: flag, anthem, etc.
Restructure Regional Governance/Borders
Chances are the governments of each original empires worked differently in many respects. In the long term, this will have to change. Both governments will need to be restructured to act as one. As part of the restructuring redraw regional boundaries to encourage weakening of historic associations in favor of new ones. (some will remain wholly east or west, but many will not.)
Office of Integration Facilitation
Department of the new government specifically chartered to identify and remove obstacles. Openly would have a large hand in determining the optimal restructuring listed above, and administer the melting pot projects below. Behind the scenes would hook into a network of operatives to collect/spread unofficial information.
Help improve acceptance of unification, discredit problematic people/organizations/practices.
Depending on the level of sophistication, this may not be possible. The basic idea is to bill the unification as a reunification and find(or make up) history of common roots along with tales of the magnificence of the past and restoring the glory of what once was. Reasons/blame for the original split should be placed elsewhere (punishment from heaven, evil plots of foreign (or long since defeated) powers.
If everyone follows the same god, or the gods are part of the same pantheon, the union could be advertised as "blessed" by those deities (assuming they will not actually show up and correct you)
Turn the country into a melting pot. This goes along with the building of highways. Differences in culture become muted and disappear when constantly in contact with others. Misunderstandings and prejudices
Migration and Inter-marriage
Have families of each side relocate to the other. Additionally have individuals marry across historic boundaries. This should be done at all social levels. How it is carried out will depend on the tools/funds the government has at its disposal as well as the size of the population and scale of the new empire. Can be anything from weak encouragement, to a relocation lottery enforced by the military. Somewhere in the middle where the crown buys up migrant's homes and sells them to other migrants at some discount.
This is more of a long-term plan and will take a few generations for full effect.
Create a national education program (if one does not already exist). Require students spend some significant portion of their terms in exchange in other regions. Exchange assignments should favor cross-country placement.
Depending on the metaphysics of your magic, it could create additional difficulties (maybe major regional dependencies/identity that can't be avoided) or make them all go away (massive charm spell). That's the nature of magic though...
Nothing like a good war to cement alliances and make new friends.