Wildcards worked for me when the string I was searching for could be entered manually. However, I wanted to store this string in another cell and refer to it. I couldn't figure out how to do this with wildcards so I ended up doing the following:
A1 is the cell containing my search string. B and C are the columns within which I want to count the number of instances of A1, including within strings:
=COUNTIF(ARRAYFORMULA(ISNUMBER(SEARCH(A1, B:C))), TRUE)