What you have to do to play palace together: one of your friends (or you but the other way round is easier) will have to set up a cross world party in party finder. Make a private party so you can set a password. You then can access pf on your world and join their group. Apart from hanging out together, chatting and queuing for duties will work as they normally would. I haven't tested this myself, but entering palace of the dead should also work like that, just have your party leader talk to the Npc. You all probably gonna have to be in Quarrymill for this to work, if you're on the same server you have to, so I don't see why this should be different in cross world.
Side note, I found out that if you unlock Gold Saucer and queue for the instances Triple Triad Battle Hall you can actually meet players from other servers there.