Ruby, 32 characters

s=->x,y{y=~/#{[*x.chars]*".*"}/}

This solution returns nil if x isn't a subsequence of y and a number otherwise (i.e. ruby equivalents to false and true). Examples:

p s['','z00']        # => 0   (i.e. true)
p s['z00','z00']     # => 0   (i.e. true)
p s['z00','00z0']    # => nil (i.e. false)
p s['anna','banana'] # => 1   (i.e. true)
p s['Anna','banana'] # => nil (i.e. false)

Python (48 chars)

import re;s=lambda x,y:re.search('.*'.join(x),y)

Same approach as Howard's Ruby answer. Too bad about Python's need to import the regex package and its "verbose" lambda. :-)

Haskell, 51 37

h@(f:l)%(g:m)=f==g&&l%m||h%m;x%y=x<=y

Thanks to Hammar for the substantial improvement. It's now an infix function, but there seems to be no reason why it shouldn't.

Demonstration:

GHCi> :{
GHCi| zipWith (%) [""   , "z00", "z00" , "anna"  , "Anna"]
GHCi|             ["z00", "z00", "00z0", "banana", "banana"]
GHCi| :}
[True,True,False,True,False]

Python, 59 characters

def s(x,y):
 for c in y:
  if x:x=x[c==x[0]:]
 return x==""

I figured my answer would be better expressed in Python.

Edit: Added r.e.s.'s suggestions.

GolfScript (22 chars)

X[0]+Y{1$(@={\}*;}/0=!

Assumes that input is taken as two predefined variables X and Y, although that is rather unusual in GolfScript. Leaves 1 for true or 0 for false on the stack.

C (52 chars)

s(char*x,char*y){return!*x||*y&&s(*x-*y?x:x+1,y+1);}

Test cases

Burlesque (6 chars)

6 chars in Burlesque: R@\/~[ (assuming x and y are on the stack. See here in action.)

PHP, 90 characters

<?function s($x,$y){while($a<strlen($y))if($y[$a++]==$x[0])$x=substr($x,1);return $x=="";}

C #, 70 113 107 90 characters

static bool S(string x,string y){return y.Any(c=>x==""||(x=x.Remove(0,c==x[0]?1:0))=="");}

Scala 106:

def m(a:String,b:String):Boolean=(a.size==0)||((b.size!=0)&&((a(0)==b(0)&&m(a.tail,b.tail))||m(a,b.tail)))

CoffeeScript 112 100 95 89

My first attempt at code golf... hope I don't shame my family!

z=(x,y)->a=x.length;return 1if!a;b=y.indexOf x[0];return 0if!++b;z x[1..a],y[b..y.length]

Edit: turns out Coffeescript is more forgiving than I thought with whitespace.

Thanks to r.e.s. and Peter Taylor for some tips for making it a bit sleeker

C - 74 71 64

This doesn't beat Peter Taylor's solution, but I think it's pretty fun (plus, this is a complete working program, not just a function)

main(int c,char**v){for(;*v[1]!=0;++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(int c,char**v){for(;*v[1];++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(c,v)char**v;{while(*v[1])v[2]+=*v[1]++==*v[2];return*v[2];}

And ungolfed:

main(int argc, char** argv){
   char * input = argv[1];
   char * test  = argv[2];

   // advance through the input string. Each time the current input
   // character is equal to the current test character, increment
   // the position in the test string.

   for(; *input!='\0'; ++input) test += *input == *test;

   // return the character that we got to in the test string.
   // if it is '\0' then we got to the end of the test string which
   // means that it is a subsequence, and the 0 (EXIT_SUCCESS) value is returned
   // otherwise something non-zero is returned, indicating failure.
   return *test;
}

To test it you can do something like:

./is_subsequence banana anna && echo "yes" || echo "nope"    
# yes
./is_subsequence banana foobar && echo "yes" || echo "nope"    
# nope

Python, 66 62 59 58 chars

Kind of a fun solution, definitely a neat problem.

def f(n,h,r=0):
 for c in h:r+=n[r:r+1]==c
 return r==len(n)

Mathematica 19 17 27

LongestCommonSequence returns the longest non-contiguous subsequence of two strings. (Not to be confused with LongestCommonSubsequence, which returns the longest contiguous subsequence.

The following checks whether the longest contiguous subsequence is the first of the two strings. (So you must enter the shorter string followed by the larger string.)

LongestCommonSequence@##==#& 

Examples

LongestCommonSequence@## == # &["", "z00"]
LongestCommonSequence@## == # &["z00", "z00"]
LongestCommonSequence@## == # &["anna", "banana"]
LongestCommonSequence@## == # &["Anna", "banana"]

True True True False

The critical test is the third one, because "anna" is contained non contiguously in "banana".

C, 23:

while(*y)*x-*y++?0:x++;

result in *x

http://ideone.com/BpITZ

CoffeeScript 73

Here's an alternative CoffeeScript answer, using regexes instead of recursion:

z=(x,y)->a='.*';a+=c+'.*'for c in x;b=eval('/'+a+'/');(y.replace b,'')<y

If the haystack matches a very greedy regex constructed from the needle, it will be replaced with an empty string. If the haystack is shorter than it started, the needle was a subsequence.

Returns false when x and y are both empty strings. Think we need a philosopher to tell us if an empty string is a subsequence of itself!

(Posted as a separate answer from my previous because it feels different enough to justify it).

A sort of anti-solution generating all subsequences of Y:

Python 93

l=len(y)
print x in[''.join(c for i,c in zip(bin(n)[2:].rjust(l,'0'),y)if i=='1')for n in range(2**l)]

Ruby 32 30 28

f=->a,b{b.match a.tr'','.*'}

This will return MatchData instance if a is subsequence of b or nil otherwise.

Old version that find substring instead of subsequence

Ruby 15

f=->a,b{!!b[a]}

Using String#[](str) method that returns str if str is a substring of self and !! to return Boolean if returned value can be usable as boolean (and don't need to be true or false) then it can be only 13 chars:

f=->a,b{b[a]}

It will return nil if a is not a substring of b.

APL (31)

String handling is a bit lacking in APL.

{(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N}

usage:

      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'anna' 'banana'
1
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'Anna' 'banana'
0
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} '' 'banana'
1

Python 132

Similar to Daniero's. Not the easiest solution, but it was fun to try. I'm new to Python, so I'm sure I could make it shorter if I knew a little bit more.

def f(i):
    s=x;j=0
    while j<len(s):t=~i%2;s=[s[:j]+s[j+1:],s][t];j+=t;i>>=1
    return s==y
print True in map(f,range(1,2**len(x)))

Javascript, 104 chars

function _(x,y){f=true;for(c in x){if(y.indexOf(x[c])>-1)y=y.replace(x[c],"");else{f=!f;break}}return f}

Ungolfed

function _(x,y){
f=true;
    for(c in x)
    {
        if(y.indexOf(x[c])>-1)
           y=y.replace(x[c],"");
        else {
            f=!f;
            break;
        }
    }
    return f;
}

Python - 72

def f(a,b):
 c=len(a)
 for i in b:a=a.replace(i,"",1)
 print len(a+b)==c

C, 120

main(i,c){char x[99],y[99];c=0;gets(y),gets(x);for(i=0;y[i]!='\0';)c+=y[i++]==x[c]?1:0;puts(x[c]=='\0'?"True":"False");}

PowerShell, 38

$args[1]-clike($args[0]-replace'','*')

Of course, any such regex- or pattern-matching-based solution has severe performance problems with longer strings. But since shortness is the criterion ...

J (20 chars)

(<x)e.(#:i.2^#y)<@#y

The input is given in the variables x and y. It makes a list of all subsequences of y, so don't use it for very big strings.

SWI-Prolog, SICStus

The built-in predicate sublist/2 of SICStus checks whether all the items in the first list also appear in the second list. This predicate is also available in SWI-Prolog via compatibility library, which can be loaded by the query [library(dialect/sicstus/lists)]..

Sample run:

25 ?- sublist("","z00").
true.

26 ?- sublist("z00","z00").
true .

27 ?- sublist("z00","00z0").
false.

28 ?- sublist("aa","anna").
true .

29 ?- sublist("anna","banana").
true .

30 ?- sublist("Anna","banana").
false.

The byte count can technically be 0, since all we are doing here is querying, much like how we run a program and supply input to it.

Python (72)

import itertools as I;any(tuple(X)==Z for Z in I.permutations(Y,len(X)))

BASIC: : 18 chars

print instr(a$, b$)

Heh heh heh. Good old QBasic.

bash & grep: 39

grep "$(sed 's/./&.*/g'<<<"$X")"<<<"$Y"

The return value of grep is the answer.