Yes, you can wing up regardless of your allied powers.
Whatever faction you choose will determine what systems are hostile to you, so choosing warring powers may lead to one of you always being chased if the other is trying to take advantage of Power bonuses by travelling in their allied systems. You may even appear as a hostile to each other in some situations, but that shouldn't affect any gameplay.
Full list of Powerplay bonuses
The only benefits to choosing the same powers are that you will most likely travel together and be in the same type of Power-controlled space, and if you're both allied to that power, you'll both get your power bonuses, such as extra bounty cash, or ship discounts. Bounty hunting is a good example of a profession that is best done with a wingman, so it makes sense to maximize profits if you're both able to ally to a bounty-friendly Power, and get to that Power's allied space.
As far as I know, there are no gotchas related to Powers. You should be able to pick up each other's jettisoned cargo, dock together, etc. but there isn't much documentation on the subject.