Uiua, 23 21 13 bytes

^{-2 bytes thanks to Europe2048}

+1↙5°⍆⍉°△5_15

Try it!

If the answer needs to be flattened, prepend ♭ for +1 byte.

+1↙5°⍆⍉°△5_15
         °△5_15 # create a 5x15 array numbered 0-74
       ⍉       # transpose
    °⍆         # shuffle the rows
  ↙5            # take the first 5 rows
+1              # add 1 to each number

23 byte stable version:

++1×15⇡5[⍥(↙5⍏[⍥⚂15])5]

Try it!

++1×15⇡5[⍥(↙5⍏[⍥⚂15])5]
                [⍥⚂15]    # create an array of 15 random numbers from 0-1
              ⍏           # get their ordering
            ↙5             # keep the first 5
        [⍥             5] # do this 5 times
++1×15⇡5                   # add [1 15 31 46 61]

Javascript ES6, 145 Bytes

Try it online! This uses console.log because there is no alert function in NodeJS, so there are a few extra bytes there.

Z=Array;alert([...Z(5)].map((_,i)=>(r=[...Z(16)].map((_,j)=>j+1+i*15),[...Z(i==3?4:5)].map(v=>r.splice(Math.random()*r.length|0,1)[0]))).join`,`)

Explanation

Z=Array;alert( // Array is used multiple times, so I use a variable to save some bytes
    [...Z(5)].map((_,i)=>( // Array of 5, because there are 5 columns
        r=[...Z(16)] // List of all possible values for a column
            .map((_,j)=>j+1+i*15),
        [...Z(i==3?4:5)] // 5 Numbers each Column, with exception to the middle, which is 4
            .map(v=>r.splice( // Remove that value from the list after being chose
                Math.random()*r.length|0,1 // Round the random number to index it
            )[0]))) // Those commands were stored in a list, and we are finding the "r" value
            .join`,`) // Join those together

Perl 5, 58 bytes

map{my%f;@f{15*$_+++1..15*$_}++;say for(keys%f)[1..5]}0..4

Try it online!

Vyxal, 11 bytes

75ɾ15ẇƛÞ℅5Ẏ

Try it Online!

75ɾ         # range(1, 75)
   15ẇ      # Cut into chunks of 15
      ƛ     # Over each
       Þ℅   # Shuffle
         5Ẏ # Get the first five items

R, 38 bytes

cat(apply(matrix(1:75,,5),2,sample,5))

Try it online!

(another 7 years later... )

Japt, 12 bytes

75õ òF Ëá5 ö

Try it (or formatted as a Bingo card)

R, 63 51 50 49 45 bytes

Thanks to Billywob for ongoing suggestions and encouraging my competitive streak.

cat(sapply(split(n<-1:75,cut(n,5)),sample,5))

5 14 15 3 1 20 30 28 18 27 32 45 42 43 41 49 54 50 56 47 68 66 64 73 71

PHP, 86

for($o=[];25>$i=count($o);){$n=rand(1,15)+($i-$i%5)*3;$o[$n]=$n;}echo implode(",",$o);

Python 2, 84 bytes

from random import*
print sum([sample(range(1+i*15,16+i*15),5)for i in range(5)],[])

If the output as list if lists is okay there is a 75 bytes solution:

from random import*
print[sample(range(1+i*15,16+i*15),5)for i in range(5)]

Clojure - 52 chars

(map #(take 5(shuffle %))(partition 15(range 1 76)))

Example output (note that it provides the separate rows as sub-lists):

((4 1 12 10 2) (25 23 21 16 27) (39 33 45 44 43) (48 53 59 54 47) (73 71 61 64 63))

PHP 106

<?$z=1;for($i=0;$i<5;$i++){for($j=0;$j<rand(1,5);$j++){$o[]=rand($z,$z+15);}$z+=15;}echo implode(",", $o);

I'm not sure I understood correctly the problem... Can you provide a more detailed explanation?

Windows PowerShell, 51 54

I'm not sure whether I understood your task correctly, though.

(0..4|%{($x=15*$_+1)..($x+14)|random -c 5})-join','

Sample outputs:

5,9,1,7,13,26,18,23,17,22,37,33,34,41,44,50,53,59,60,58,73,72,64,69,66
14,10,13,5,1,24,29,26,17,30,34,33,43,41,38,59,50,60,49,56,71,61,72,70,68
3,11,4,5,13,27,16,25,26,22,43,34,42,32,38,51,52,49,58,54,61,70,73,71,62
1,9,13,12,4,23,25,20,26,22,40,33,35,44,37,55,47,52,59,53,74,70,75,64,69
8,6,7,1,9,16,21,23,18,17,35,41,37,38,34,60,50,57,51,59,66,75,73,74,71
11,6,13,4,1,29,27,24,22,18,40,35,41,32,43,51,54,57,58,53,74,71,69,66,64

Ruby 1.9, 48 characters

$><<(0..4).map{|i|[*1..75][15*i,15].sample 5}*?,