I can think of only one way that guns and swords could coexist. While guns are great at killing humans and smaller critters, there might be quite a few monsters and demons out there that cannot be harmed by bullets but can still be cut into pieces by a good old sword. That way, both weapons have their validity. Having a reputation as a gunslinger might even be less impressive to some people than that of a master swordsman, and swords duels might be as common as pistol duels. You would probably need both skills to survive anyway.
A western without guns would seem sort of weird, because some of the iconic moments would simply not be possible. I wouldn't say it is impossible to do, but you would have a hard time establishing it against the readers expectation, but done well it should not be a problem. If you want a reason why there are no guns, magic as described below could be common enough so nobody ever bothered inventing them.
As for magic, I have one thing to say at first: I hate wands.
Don't get me wrong, there are places where they fit in, but magical western just isn't it. The whole western setting is rough and unpolished, so the style of magic should reflect that. Singular abilities, for example a fireslinger who can... well, sling fire. A natural gun if you will, with the same power and accuracy a gun would have. He would even have to "load" his power, engulfing his hand in fire with his will, which (coincidently!) takes about the time someone else would need to draw a gun.
Let's look at a duel. A gunslinger against a fireslinger. Both draw back their coats, the first reveals his holster holding his gun, he puts his hand next to it in the typical close up gesture. The second one reveals that he does not have a holster, maybe to intimidate the opponent, because he knows what he has coming. He too holds his hand next to where his holster would be, a nervous twitch in his index finger. On the draw, the fireslinger quickly stretches his hand, engulfing it in flame, then thrusting it forwards to throw a bolt of fire at his opponent.
Or a bar fight, some guys have their guns out, the fireslinger has his hand ablaze, when the sheriff comes in and tell him to put it out (like he would otherwise tell someone to drop a gun).
The whole spellbook, magic staff, whatever stereotype wizards stuff you have should probably not come up that often. That is "old world magic". There might still be some of those around, because a full blown sorcerer would make a great gang boss. Restricted in the old world, they can freely follow their dark desires in the new land.
Other kinds of magic could be less fight oriented. For example, I have the concept for a character called "First Aid Kid", You can guess his magical talent
At a whole, if you stay mainly in the western genre, magic should probably just partially replace certain iconic objects and only for some people, while those items are still around.
Native magic (if you have an equivalent of native americans) would probably be more like druids or shamans (totems, dancing, influencing plants and animals, shifting into an animalform, stuff like that), and some of the settlers might even be learning some of it or something similar, especially scouts or similar characters would profit from this. And it is a great source for some cultural conflict. Could be even more interesting, if they use bows but there are no guns.
The fireslinger magic (any magic that does not fall under the shaman/druid category really) could either be hereditary or come from some item (no wands!). If you don't have guns, it should probably be items, so they replace the guns.