A variable defined in the module outside of any function is considered a global variable. To modify a global variable inside of a function, you must write global variableName inside of the function.

You did this, however, that variable is only defined in your function, it must also be declared outside of the function to be considered a global variable. If not, it will be local to your function, despite the global in front of it.

TL;DR Also declare the variable outside of your function.

EDIT (I was wrong):

By writing global variableName in a function and executing said function, it does make the variable a global variable; if not you would be getting a NameError when you tried to print it.

The reason that you're getting a 0, however, is because everytime you call your function, you initialize count to 0. Nonetheless, the solution about still holds.

Move count = 0 outside your fib(n) function. You only need to declare it as global count once inside the function, while the initialization should be outside. What you're doing is that you are re-initializing it with 0 every time the function is called.

import sys

count = 0

def fib(n):
    """Takes input a natural number n > 0.
        Returns n! """

    global count
    if n == 1 or n == 0:
        return 1

    else:
        if n == 2:
            print 'encountered here::: '
            count += 1
        return fib(n-1) + fib(n-2)

def main():
    x = int(raw_input('Enter a natural number > 0 :'))
    print 'Fibonacci(%d) = %d' % (x, fib(x))
    print 'Count =', count
if 1:
    main()

Although, you should avoid global variables.

global foo
foo = [1,2,3] 

Now foo can be used anywhere in the program

Put the count = 0 outside the function.