Reading Multidimensional arrays
Don't search – find. Specifically, don't iterate through all matrix entries for each character. Instead, build a dictionary that maps the characters in the matrix to a pair of indices.

Also, don't loop over indices (in message) unless you have to. Now we have:

position_lookup = dict()
for x in range(len(matrix)):
  for y in range(len(matrix[x])):
    position_lookup[matrix[x][y]] = (x, y)

for char in message:
  if char in position_lookup:
    x, y = position_lookup[char]
    cyphermessage.extend([x, y, " "])


Technically, this behaves different from the code you wrote: consider what happens when one character occurs multiple times in the matrix – I only use the last occurrence, while you append all possibilities.