The foam bonded to the velour fabric is an open cell polyurethane foam. Your best bet is to use a high temp spray grade contact adhesive like DAP Weldwood top and trim adhesive, 3-M Top and trim adhesive, or Helmitin Helmiprene, even if you have to spray or brush it on for a headliner. There is also a product called K-Grip 202 High Temp. All of those are best if sprayed. If I were you, I would invest in a cheap spray gun from Harbor Freight with at least a 2MM nozzle (They only cost about $20. Part # is 43760-6RBA) and use one of the bulk adhesives.
Do not use 3-M 74 or 77. They are general purpose adhesives and will fail if used on your headliner.
DAP makes an aerosol called Weldwood top and trim spray, and 3-M makes 08090 Super Trim adhesive. There is also a spray called Performance High Temp contact adhesive. All of those are your next best bet, but they are not really recommended for foam backed headliners. Here's a link to some of these: CLICK HERE