Code creates different plan when ran ad-hoc vs. in a stored procedure
Usual suspects:


constants in adhoc, parameters in code
mismatch of data types in code
parameter sniffing


Point 1: the optimiser can choose the best plan for the constants.
Change the constants = change the plan. A parametrised plen is resuable

Point 2 will introduce implicit conversions because of datatype precedence
eg varchar column compared to nvarchar parameter

Point 3: use parameter masking or OPTIMISE FOR UNKNOWN
Edit: To test: run stored proc, run sp_updatestats, run again. This will invalidate cached plans which is better then clearing plan cache

Edit: after jcolebrand's comment

You can disable sniffing several ways. The main 3 are


RECOMPILE. This is silly IMO.
OPTIMIZE (sic) FOR UNKNOWN
Parameter masking


Parameter masking:

DECLARE @MaskedParam varchar(10)
SELECT @MaskedParam = @SignaureParam

SELECT...WHERE column = @MaskedParam


Masking and the OPTIMIZE hint have the same effect (maybe for different reasons). That is, the optimiser has to use statistics and data distribution (Note: still under testing by Mark Storey-Smith) evaluate the parameters on their own merits ? , rather than what they were last call. The optimiser can recompile or not. SQL Server 2005 added statement level recompilation so there was less impact 

Now, why a plan with "sniffed" parameters is "sticky" compared to masked/"unknown" parameters, I'm not sure.

I've used parameter masking since SQL Server 2000 for all but the simplest code. I've noted that it is liable to happen with more complex code. And at my old job I has some report procs that I could change the plan parameter defaults. I reckon the "cargo cult" approach was easier than a support call.

Edit 2, 12 Oct 2011, after some chat


Parameter masking and OPTIMISE FOR UNKNOWN have the same effect as far as I can tell
The hint is cleaner than masking but was added with SQL Server 2008.
Parameter sniffing happens at compile time. 
WITH RECOMPILE generates a new plan each execution. This means a poor choice of defaults will influence the plan. At my last job, I could demonstrate this easily with some report code: changing parameter defaults altered the plan regardless of supplied parameters.
This MS Connect article is interesting: Suboptimal index usage within stored procedure (mentioned in one of the SO answers below)
Bob Beauchemin mentions it too


Outstanding issues


Does sniffing still apply with WITH RECOMPILE? That is, if the optimiser knows to discard the plan does it aim for re-use?
Why are sniffed plans "sticky"?


Links from SO:


https://stackoverflow.com/q/6919166/27535
https://stackoverflow.com/q/5236631/27535
https://stackoverflow.com/q/1392307/27535
https://stackoverflow.com/q/2905440/27535
https://stackoverflow.com/q/467513/27535
https://stackoverflow.com/q/272726/27535
Remus Rusanu (MS SQL team) and I had a bunfight here on SO
Whitepaper on MSDN in conjunction with my SO analysis: https://stackoverflow.com/questions/414336/why-does-the-sqlserver-optimizer-get-so-confused-with-parameters/414368#414368