Algorithm to transform a string according to occurrence count of each character
def compression(string):


Naming can be hard, but it is important to get right.  If I were to call compression('abcd'), I would expect the result length to be at-most the length of the input string.  "compression" doesn't really describe what is happening within the function.  So what exactly is your function doing?  From your description:


  I have this algorithm that counts the frequency of character occurrence in a string, and outputs a new string based on that.


A lot of nice verbs in that description you can use for a function name (serialize_frequencies?).



string = string.lower()


Does case-sensitivity have anything to do with your stated goals of calculating and serializing the frequency of characters?  It depends on the context in which this function is used.  Case-sensitivity isn't always required.  If you really want to provide a mechanism for case-insensitive frequency generation, consider a toggle parameter or another function that transforms the input then calls this function.

serialize_frequencies(string, case_insensitive = False):
    if case_insensitive:
        string = string.lower()




    freq_count = {}

    for index, char in enumerate(string):
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1


A function that performs a single operation is simpler to understand, test, and reuse.  Don't be afraid to break functions up into suitable logical parts and parameterize.  

enumerate is a nice utility when you need to iterate through a sequence but also want to know the index.  Since you don't need the index, you can just iterate through the string itself.

    for char in string:
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1


With that said, Python's collections includes a dictionary sub-class to count frequencies (Counter).

    freq_count = Counter(string)




    return_string = ''
    for key in freq_count:
        return_string += key + str(freq_count[key])


If you want to iterate a dictionary by its key-value pair, Python's built-in dictionary includes the method items().

    return_string = ''
    for key, value in freq_count.items():
        return_string += key + str(value)


You can write the loop that appends each pair using the string method join.

    return_string = ''.join(k+str(v) for k,v in freq_count.items())




    print(return_string)


Debugging artifact?




  My question is, am I making this algorithm less efficient by using dict to memoize values.


No.  But as 200_success has noted, calling compression('abcd') might result in 'a1b1c1d1' or 'c1d1b1a1' depending on the implementation.  Ordering for the built-in dictionary is arbitrary and could change between implementations, versions, or possibly application executions.  If ordering matters, then you should use a sorted container (OrderedDict, SortedDict) or manually sort the resulting dictionary before serializing.