Python3, 377 bytes

def f(a,b):
 q,c=[(a,b,[])],0
 for a,b,o in q:
  if[]==a or len(a)>len(b):c+=[]==a;continue
  q+=[(a,b[1:],o)]
  if[]==o:
   Q,S=[(a[0],0,[])],[]
   for A,I,O in Q:
    if[]==A:S+=[O];continue
    if I<len(b[0]):Q+=[(A,I+1,O)]+[(A[1:],I+1,O+[I])]*(A[0]==b[0][I])
   q+=[(a,b,j)for j in S]
  elif all(A==B for A,B in zip(a[0],[b[0][t]for t in o])):q+=[(a[1:],b[1:],o)]
 return c

Try it online!

Ruby 448

class Array
alias t transpose
alias z size
alias e each
alias s select
end

def x
v=[]
while(w=gets.chop).size>0 do
v<<w.split('')
end
v
end

def w(i,j)(0...i).to_a.combination(i-j).to_a end

a=x
n=a.z
a=a.t
o=a.z
b=x
q=b.z
r=b[0].z
w=['.']
y=w*r
z=w*q
f=[]
w(q,n).e{|u|w(r,o).e{|v|
h=b.dup
u.e{|i|h[i]=y}
h=h.t
v.e{|j|h[j]=z}
h=h.t
f<<h if(h.s{|i|i!=y}.t.s{|i|i!=w*n})==a}}
p f.z
puts
f.e{|b|b.e{|i|k='';i.e{|j|(k<<' ')if k.size>0;k<<j}
puts k}
puts}

Haskell, 364 chars

m=map
l=length
u=unlines
v=reverse
z=zip[0..]
q s=p(lines s)[]
e i a=[a!!j|j<-i]
main=g.w.q=<<getContents
g x=(print.l)x>>(putStr.u.m u)x
c 0=[[]];c n=let x=m(m(1+))$c(n-1)in x++m(0:)x
p(c:x) a|c==""=(v a,fst$p x[])|1<2=p x(c:a);p[]a=(v a,[])
w(a,b)=[m(\(p,r)->m(\(q,x)->if(elem p i&&elem q j)then(b!!p!!q)else '.')$z r)$z b|i<-c.l$b,j<-c.l$b!!0,a==(m(e j).e i)b]

Ungolfed Version, 716 chars

parse (c:x) a | c == "" = (reverse a, fst$parse x [])
              | otherwise = parse x (c:a)
parse [] a = (reverse a, [])
readMat s = parse (lines s) []

choose 0 = [[]]
choose n = let
  x = map (map (1+))$choose (n-1)
  in x ++ map (0:) x

select ix a = [a!!i | i<-ix]

for = flip map
make b (ix, jx) = 
  for (zip [0..] b) (\(i,r) ->
    for (zip [0..] r) (\(j,x) ->
      if elem i ix && elem j jx
      then b!!i!!j
      else '.'
    )
  )

main = do
  s <- getContents
  let (a, b) = readMat s
      (n, m) = (length b, length.head$ b)
  let ans = [make b (ix, jx) | ix <- choose n, jx <- choose n, 
              a == (map (select jx).select ix$ b)]
  print$ length ans
  putStrLn$unlines.map unlines$ ans

Python 2 with Numpy, 342 chars

from numpy import*
from itertools import*
import sys
S=str.split
C=combinations
R=range
a,b=[mat(map(list,S(x)))for x in S(sys.stdin.read(),'\n\n')]
n,m=b.shape
o,p=a.shape
z=[]
for i in product(C(R(n),o),C(R(m),p)):
 i=ix_(*i);e=b[i]
 if all(a==e):f=copy(b);f[:]='.';f[i]=e;z+=[f]
print len(z)
for x in z:print'\n'.join(map(''.join,x))+'\n'

Output Example

5
a..bb
a..ba
.....
.....

ab.b.
.....
.....
ab.a.

ab..b
.....
.....
ab..a

.....
.abb.
.aba.
.....

.....
a.bb.
.....
a.ba.

Mathematica, 186 chars

{a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]

Example:

In[1]:= {a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]  
? abb aba
? ababb aabba babab abbaa

Out[1]= {5, {a . . b b, a b . b ., a b . . b, . . . . ., . . . . .}}
             a . . b a  . . . . .  . . . . .  . a b b .  a . b b .
             . . . . .  . . . . .  . . . . .  . a b a .  . . . . .
             . . . . .  a b . a .  a b . . a  . . . . .  a . b a .

APL (160)

{∆,⍨⍴∆←⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨⊃¨∘.∧/¨∆/⍨⍺∘≡¨⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆←,⊃∘.,/⊂¨¨K{⍵=0:⊂⍺/1⋄~(⍳⍺)∘∊¨⍵{⍺=1:(⍳⍵)⋄∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵}⍺}¨(K←⍴⍵)-⍴⍺}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬

Output:

      {∆,⍨⍴∆←⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨⊃¨∘.∧/¨∆/⍨⍺∘≡¨⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆←,⊃∘.,/⊂¨¨K{⍵=0:⊂⍺/1⋄~(⍳⍺)∘∊¨⍵{⍺=1:(⍳⍵)⋄∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵}⍺}¨(K←⍴⍵)-⍴⍺}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬
abb
aba

ababb
aabba
babab
abbaa

 5  .....  .....  ab..b  ab.b.  a..bb  
    a.bb.  .abb.  .....  .....  a..ba  
    .....  .aba.  .....  .....  .....  
    a.ba.  .....  ab..a  ab.a.  .....  

Explanation:

• {...}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬: read the two arrays from the keyboard, and return them as two matrices. Reduce the following function over the list of the two matrices.

• ∆{...}¨(∆←⍴⍵)-⍴⍺: get the height and width of each of the matrices. In both the width and the height, get a list of possible lines to drop.

  • ⍵=0:⊂⍺/1: if the matrices are the same length in a dimension, never drop any lines from that dimension. Otherwise:

  • ⍺=1:(⍳⍵)⋄: If the difference is one, try to drop each line

  • ∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵: otherwise, drop each possible combination of ⍺ lines.
• ∆←,⊃∘.,/⊂¨¨: combine each height mask with each width mask, giving all possible combinations to make the second list the size of the first.
• ⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆: for each possible combination, remove those lines from the second matrix.
• ∆/⍨⍺∘≡¨: drop all the ones that are not equal to the first matrix, giving the solutions.
• ⊃¨∘.∧/¨: for each of the possible solutions, make a matrix with 0 where a dot should go and 1 where the corresponding character from the first matrix should go.
• ⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨: for each of these, flatten both the second matrix (,⍵) and the matrix of dots (,⍺), and take either the character or a dot for each position ({⍺:⍵⋄'.'}¨). Then reshape it to the shape it had before ((⍴⍵)⍴).
• ∆,⍨⍴∆: give the amount of solution, and each solution.