This is another anime in which a powerful hero (or anti-hero) character is accompanied by a much younger and relatively powerless companion. This is a theme which is used fairly often, in my experience, for example it is also used in Claymore and Samurai Champloo.
Another similarity this show has with Trigun is that the opening theme is not an abbreviated version of a previously existing song. This opening theme was composed specifically for GunXSword and is simply titled "GunXSword." The graphics on this version are not great, but it's the only one I could find that wasn't just a slide show collection set to the theme music. Keeping in my that this story is western-themed, I think you should easily be able to hear where some of the inspiration for it came from. The composer is Kōtarō Nakagawa, who has created music for numerous anime and video games.