Because the string is immutable (as would a tuple), it is stored with the bytecode object for the function. It is loaded by a very simple and fast index lookup. This is actually faster than a global lookup.

You can see this in a disassembly of the bytecode, using the dis.dis() function:

>>> import dis
>>> def foo(s):
...     c_string = "hello"
...     if s == c_string:
...         return True
...     return False
... 
>>> dis.dis(foo)
  2           0 LOAD_CONST               1 ('hello')
              3 STORE_FAST               1 (c_string)

  3           6 LOAD_FAST                0 (s)
              9 LOAD_FAST                1 (c_string)
             12 COMPARE_OP               2 (==)
             15 POP_JUMP_IF_FALSE       22

  4          18 LOAD_GLOBAL              0 (True)
             21 RETURN_VALUE        

  5     >>   22 LOAD_GLOBAL              1 (False)
             25 RETURN_VALUE        
>>> foo.__code__.co_consts
(None, 'hello')

The LOAD_CONST opcode loads the string object from the co_costs array that is part of the code object for the function; the reference is pushed to the top of the stack. The STORE_FAST opcode takes the reference from the top of the stack and stores it in the locals array, again a very simple and fast operation.

For mutable literals ({..}, [..]) special opcodes build the object, with the contents still treated as constants as much as possible (more complex structures just follow the same building blocks):

>>> def bar(): return ['spam', 'eggs']
... 
>>> dis.dis(bar)
  1           0 LOAD_CONST               1 ('spam')
              3 LOAD_CONST               2 ('eggs')
              6 BUILD_LIST               2
              9 RETURN_VALUE        

The BUILD_LIST call creates the new list object, using two constant string objects.

Interesting fact: If you used a list object for a membership test (something in ['option1', 'option2', 'option3'] Python knows the list object will never be mutated and will convert it to a tuple for you at compile time (a so-called peephole optimisation). The same applies to a set literal, which is converted to a frozenset() object, but only in Python 3.2 and newer. See Tuple or list when using 'in' in an 'if' clause?

Note that your sample function is using booleans rather verbosely; you could just have used:

def foo(s):
    c_string = "hello"
    return s == c_string

for the exact same result, avoiding the LOAD_GLOBAL calls in Python 2 (Python 3 made True and False keywords so the values can also be stored as constants).