This is my first guide so please leave a comment instead of just a down-vote, thanks! :)

My aim with this build is to take advantage of the red Lizard buff's slow and Caitlyn's huge range to make her a very annoying ranged DPS to come up against. Obviously, you can have huge damage with Madred's, Infinity Edge, Phantom + anything else but all three of those are incredibly expensive, you can certainly use this as a jumping point to that build as you can farm quite well with this but that'd only be for a very long game.

The way I think of it is that if you have two Caitlyn's in a normal game and the other is using M's, IE, PD and you're using this, your build will be finished first and you'll probably kick her *** up and down before she can afford two out of those three items. Sure, you can get these quickly if you're steam-rolling but if it is a close game or your team is losing, this build is relatively cheap so that you can still be viable and have a chance to win.

The second build is for use when you're up against a CC heavy team. It follows the same philosophy of cheap items and attack speed to wipe the floor with your enemies before it gets to late game. I took cleanse and QSS for two cleanses and cheap magic resistance. Obviously, Banshee's is the best choice for Magic Resist but if you're cash-starved and cc-focused you need it, bro. I also assumed you wouldn't stay alive to make Bloodthirster useful so I went with Black Cleaver for extra attack speed and armor shredding. This is a contingency build and the rest of the guide should be read as if you were using the first build.

Your masteries are all over the place but there is method to my madness.

-Improved Summoner Spells are a natural choice
-Extra crit chance to synergize with Zeal and Elixir
-Extra Attack speed and armor penetration. I don't go any deeper than this because it means I can't get the Defense masteries for armor and magic resist, she's quite squishy and I feel uncomfortable without the extra boost from these
-I maxed extra experience and only invested in half of extra mana but you could do the opposite as it is very easy to run out of mana with Caitlyn, and if you miss a kill because you did not have mana then you are very bad. For this reason I have mana regen runes & the mastery to keep it up. If you're really having problems, buy a cheap *** Chalice and sell it later
-Jungle buff duration. I emphasize making use of the Red buff and this lets you keep it for longer, no brainer. Don't take this if you're using frozen mallet instead of red
-1/3 extra movement speed to get away from melee characters

I choose Exhaust and Ghost to get away from or shut down melee characters that will ruin your day like AP-flash Sion, low health Trynd and Olaf, etc.

Other choices are:

Teleport - Great for getting to a teamfight or for joining a creep push and using your disgusting attack speed to destroy a tower and run away

Clarity - As I said, if you miss a kill because you didn't have enough mana to ult, you're bad and should reconsider how you're playing. Take clarity until you get used to it, then use exhaust and a Chalice that you sell later.

Cleanse - I use it in the contingency build against cc-heavy teams (usually you'd only do this for ranked play counter picking, you can't tell who you're coming up against in normal)

Flash - Get Out of Gank free card

Clairvoyance - It sounds ******ed but a very low enemy gets into the fog of war and you can kill him with your ult, drop clair on him and use the gained sight to kill him.

Heal - Maybe this would work well if you're new? It's saved people from me in the past but usually it saved them when they were overextending, something you shouldn't be doing as a squishy carry.

Ignite - The extra damage is paltry compared to what you can do, it's good for killing low health people running away but your ult does that. The reduced healing is good but you can get that with Executioner's Calling (lifesteal, crit chance and the same effect as an active)

Fortify, Rally, Revive, Smite - only if you want to encourage a queue dodge

This build emphasizes upping your Piltover Peacemaker (Q) first for it's high damage and because it is a fantastic long-range poke.

Next you should max your 40 Caliber Net (E) to reduce it's cooldown and allow you to move around. Always remember the knockback feature as it is quite handy for getting extra distance on an exhausted enemy; the other great use is to net behind you to push yourself forward, perhaps just putting you in range for your ult or a killing shot.

Yordle Snap Traps are nice for the snare and vision but you can have very few of them and they're quite visible (compared to Nidalee's nearly invisible but still visible traps). Yordle traps are great but you have to place them smart to maximize their effectiveness. Let's say you're running away from enemies in the river towards dragon and then mid, drop a trap in the bush to dragon's left as you run towards it and then through it, this gives the trap time to arm and save you. If you drop your trap at the edge of your range and run towards it, by the time you reach the trap it will usually have armed itself, keep that in mind.

As I said in the introduction, the philosophy of this build is to make use of your passive, Head Shot, and your long range to be a very annoying ranged DPS. This would probably work best as a counter pick against a squishy team but you'll need to significantly re-tool the build if you go up against a lot of CC.

Starting item is a Doran's Blade for extra health, damage and some lifesteal that will help you stay in the lane, but I would only use this as staying power >50% health and not against people with high burst capabilities as the lifesteal is very low so you have to auto-attack for awhile to get any health back - if you're only shooting for last hits and harassing the enemy champs you'll not improve your health fast enough. Sell your Doran's Blade as soon as you need the inventory space or if you're very close to finishing an item.
Another possibility for a good starting item would be Boots of Speed + 3 potions, giving you a big movement speed bonus right away to let you harass and position yourself much better.

First trip back should be either Boots of Speed or Dagger, extra movement speed or extra attack speed. Ideally you won't return with <920g which allows you to get Berzerker's Greaves for a healthy attack and movement speed boost. Immediately after I get the cheap (1195g) Zeal for attack speed, crit chance, and movement speed to help you farm and escape from ganks.

Pick up Recurve Bow or Dagger as your first item towards Sword of the Divine for a huge attack speed increase (this point will get you to about 1.7 attacks per second IIRC) which will help for farming your BF Sword. I chose Bloodthirster for the snowballing damage and lifesteal but if you're dying enough to lose those stacks, you're much better off choosing Black Cleaver for the extra ArPen and attack speed. If this is your game then use your runes, Sword's active, Black Cleaver, and Last Whisper to get as close to true damage as you reasonably can.

At any point after finishing your BF Sword derivative item you should always have Elixir of Agility up for extra attack speed and crit chance, it's very cheap so you have no excuse not to keep it up at all times as it will help you immensely.

At this point, I buy Negatron Cloak and Chainmail at the same time (1440g) for boosts in your defensive stats, if they have a lot of CC then finish Banshee's first. Don't put off your GA for too long as it will help dramatically if you're being focused and is incredibly good late game when a death can mean GG. I usually leave Phantom Dancer to last because it is quite expensive and you honestly don't need the extra attack speed or crit chance, you're head shotting so quickly it's basically a crit, anyway.

Other fantastic options:

Glacial Shroud - Great armor, cooldown reduction, and mana, all things you're lacking and for pretty cheap. Beastly upgrade to Frozen Heart. I chose Guardian Angel because it boosts Armor & Magic Def and the passive could clinch a game

Last Whisper - % based armor penetration and extra damage, not too expensive. I neglected it because you already get a lot but it would be quite good for getting close to true damage

Black Cleaver - I mention quite a few times that this item is good for Cait but I prefer Bloodthirster. Anyway, you attack so quickly that the armor shredding is fully stacked in 2.5-3.5 seconds, just about then you will have a headshot up, hit Sword's active for a huge headshot. Rinse, repeat.

Stark's Fervor - Aura item giving life steal and attack speed, both great bonuses. If you're not going to upgrade your Zeal then I could see replacing it with this, Vampiric Scepter is quite cheap (400g) and upgrading to the 17% Badge of Valor is ~600g. Use this if you have Kassadin, Taric, or Sivir on your team and they aren't. This is a great item for your party and these heroes in particular (if you don't know why, Kass and Taric recover mana through melee, Taric reduces his healing cooldown by attacking, and Sivir ricochets much faster) but it works best on someone who is an aura bot (Janna with Aegis, Soul Shroud, Frozen Heart, Starks, for example)

Madred's Bloodrazor - Eschewed because of it's expensive nature, however, if you had Sword of the Divine and Madred's you'd have disgusting attack speed and bonus magical damage so I could see an alternative build of cc boots/Madreds/Sword/lifesteal/survivability items x 2 working quite well, give it a try and let me know how it works.

-Long range combined a with slow makes it difficult to escape
-Very high attack speed combined with armor penetration means that you rack up headshots and Sword of the Divine's bonus magic damage very quickly which makes up for not having a huge base damage
-High attack speed makes it short work to destroy structures during a push
-High attack speed means you can farm creeps easily and quickly which gets your Bloodthirster snowball rolling and extra lifesteal will help keep you alive
-If the enemy carry dies and Guardian Angel keeps you alive, that can be GG

-As ranged physical DPS you are very squishy and you're not countering that until your last two items, this means you need to have good map awareness and try not to go alone or you could risk being ganked pretty severely
-Being very squishy means your susceptible to ganks and CC
-Countered by: Thornmail and dodge. Sivir is not as bad for dodging but if you're shooting at Jax and he dodges it could end poorly for you. There's nothing you can do about thornmail (other than lifesteal and armor to mitigate damage you do to yourself) but the Sword of the Divine's active will give you at least eight seconds of armor-penetrating undodgeable shots to make Jax think twice about trying to kill you

I'm sure many people will take the mid lane so that they can level up faster and get more minion kills but I think Cait works very well in the side lanes. I usually play with a good friend of mine and we prefer to lane together so this contributes to my decision; both seem like great options.

Mid
-No one to compete against for last hits
-No experience sharing so you level up your poke faster
-If they have a jungler it is very likely that you will be ganked first because you are 1) alone and 2) squishy
Getting a big farm on early is fantastic, counter your vulnerable position with traps in the bushes. You and your team should also be using wards at dragon at the VERY least, drop a few more in the bushes to keep an eye out for incoming ganks.

-Depending on your lane partner, you can have a babysitter or someone with CC that could help you catch an early kill
-Having a lane partner means you have someone else to help you and for you to help, protect eachother from ganks proactively (map awareness, wards, and MIA calls) as well as reactively (Xin lunges forward to 3TS you, for example)
-Side lanes let you attack from the bushes, allowing you to build head shots twice as fast. Last hit creeps from the bushes and harass enemy champs with a head shot when you can
-Shared XP
-If you have a greedy lane partner who is better than last hitting than you it could hurt your farming and defeat your usefulness. In one game, I saw a Lux and Ashe laning together, Ashe had 61 minion kills compared to Lux's 17. Be smart about your last hitting and talk to your partner if they are hogging
-If you are laning against someone with map control then you should be extremely wary of the bushes, if you go into the bushes to shoot at creeps it will usually leave you in a position where it is much more difficult to block a skill shot with a creep or dodge with your own movement. I would absolutely not go into the bush against someone like Blitz, Lux, or Morgana since the two females can snare you for a painful combo and Blitz will do some serious damage against you if he lands a grab. If you find yourself against such a combo, IMO, the only thing that should be in the bushes is a trap for them to give you sight and steer clear of their shots

No matter which lane you choose, you should always drop traps in the bushes or danger areas to warn you of any incoming enemies. For example, the bot lane has a bush on the purple side of the river, put your trap at the "top" of bush, closer to the golem, so anyone entering the bush from that direction is immediately snared. If they walk into the bush, they would see that your trap and easily avoid it, so place them carefully. Obviously, do not face check bushes, especially since you have two ranged pokes/skill shots you can use to check for you. Listen for the hit sound if you launch a net and be wary if you do hear something.

In order for this build to work properly/well, you *need* a slow!

If you have a jungler they will, of course, take the red buff in early game which is fine, but you need some sort of slow to keep enemies in range while you pummel them. Frozen mallet is a good choice with it's permanent slow and extra health but I did not include this in the build because it is very expensive to finish when you compare it to the fact that the red buff is free and quite long (With jungle masteries). If you have a Cho with Rylai's (slowing normal and magic attacks) or another teammate that can slow often (Anivia, Nunu, etc) then you can forgo this but I prefer to be able to apply slows to people I want to kill rather than whoever my teammates happen to hit; you would also need to always be with that person, etc, it's just easier to apply it yourself.