Simple fuzzy text search algorithm
Blocks longer than one line are conventionally written using do…end rather than braces.
Code of the form

out = []
list.each { |l| ... out.push(something) }


… would be better expressed as

out = list.collect { |l| something }


Besides being slightly more compact, there is a subtle difference in thinking: the former feels like "do this, then this, then this to build a result"; the latter says "transform each element like this", and it's easier to see that there is a one-to-one correspondence between input elements and output elements.
Within that block,

out = list.collect do |l|
  # Calling l.downcase! would have the side-effect of modifying
  # strings in the original list, which is impolite.
  l = l.downcase

  shared_chars = []
  key.split.each_with_index do |c, keyi|
    index = l.index(c)
    # Actually, char:c is never used and could be eliminated
    shared_chars.push(char: c, index: index, kindex: keyi) if index
  end

  distance, kdistance = 0, 0
  shared_chars.each_cons(2) do |a, b|
    distance += (b[:index] - a[:index]).abs
    kdistance += (b[:kindex] - a[:kindex]).abs
  end

  { val: l, shared_chars: shared_chars, distance: (distance - odistance).abs }
end

Furthermore,

out.sort_by! { |e| ... }
out


could just be

out.sort_by { |e| ... }


(.sort_by is defined because an Array is an Enumerable.)
I think that the whole function would be better as one chained expression:

def search(key, list)
  key = key.downcase

  list.collect do |l|
    ...
  end.sort_by do |e|
    # There's no point in adding 100 to each element
    e[:distance] - 3 * e[:shared_chars].length
  end
end