First, look at your gear carefully and decide what is ABSOLUTELY necessary. Be brutal. Do you really need that 3 mil jacket if the water is 80 plus degrees? Dive slate? Backup snorkel? Back up knife? You get the idea.
Second, really trim the clothing. Do you REALLY need a pair of shorts for every day of the week when you only wear them in the morning and the evening (and you are in swim trunks the rest of the time underwater)? Can you wash some clothing at your resort/hotel? Pare down anything that isn't absolutely necessary, just as you did with the gear.
Then, decide what gear goes in what bag. I take my computer, regs, and camera gear in my carry on bag, along with ONE change of clothes (usually shorts and t-shirt if it's a tropical destination). I pack by stowing my gear in a rolling pilot bag (important stuff first, right?) and then packing it all into place with clothing around the sides. Not only does this maximize space, but it also pads my gear. I tend to roll t-shirts and shorts instead of folding them because iit tends to use less space.
It goes without saying that if you plan on flying with gear often, you might want to invest in the lightest weight gear that will still meet your needs. Talk with other experienced traveling divers and see what they have chosen for their kit. Valuable insights can be gleaned by looking around and seeing how others solved the problem.
Welcome to diving!