I have heard a story that Lord Brahma has done Yajna in Gaya on the body of Gayasur. But I want to know the scriptural basis of this story if any or how Gaya, the place, has became famous?
Gayasura was Asura (demon) who did a severe penance. Devas with Shiva went to Vishnu and at suggestion of Lord Vishnu they went to Gayasura to grant him boon. Gayasura requested Devas to make him holiest of all things.
ऊचुस्तं वासुदेवाद्याः किमर्थ तप्यते त्वया। संतुष्टाः स्वागताः सर्वे वरं ब्रूहि गयासुर।।१५।।
Vásudeva and others spoke to him- “For what purpose, this penance is being performed by you, O Gayåsura? We have all arrived here fully satisfied. You may ask for a boon.”
गयासुर उवाच यदि तुष्टाः स्य मे देवा ब्रह्मविष्णुमहेश्वराः। सर्वदेवद्विजातिभ्यो यज्ञतीर्थशिलोच्यात्॥१६॥
देवेभ्योऽतिपवित्रोऽहमृषिभ्योऽपि शिवाव्ययात्। मन्त्रेभ्यो देवदेवीभ्यो योगिभ्यश्चापि सर्वशः।।१७।।
न्यासिभ्यश्चापि कर्मिभ्यो धर्मिभिश्च तथा पुनः। ज्ञ(य)तिपवित्रेभ्यः पवित्रः स्यां सदा सुराः।।१८।।
Gayåsura spoke– In case you are pleased with me, O Gods, Brahmā, Visnu and Maheśvara, may I be ever holier than these– than all the gods and Brähmanas; than all the Yajñas, tirthas and Silocaya (mountains); than all the sages; than even the unchanging Siva; than all the Mantras; than all the lords of Devas; than all the Yogins; than all the renouncers; than all the performers of holy rites; than all the religious ones; than all the sacred Yatis.
As he became holier than Devas, Devas were devoid of work and went to abode of Vishnu. Vishnu said,
गत्वाऽसुरं प्रार्थयस्व यज्ञार्थं देहि देहकम्। विष्णूक्त: ससुरो ब्रह्मा गत्वाऽपश्यन्महासुरम्।।२४।।
“Go and request the Asura thus, ‘Give your body for the purpose of a sacrifice’.” Urged by Visnu, Brahmá went there accompanied by Devas and saw the great Asura.
ब्रह्मोवाच पृथिव्यां यानि तीर्थानि दृष्टानि भ्रमता मया। यज्ञार्थं न तु ते तानि पवित्राणि शरीरत:।२८।।
Brahmā replied— All the tirthas (places of pilgrimage) seen by me while on the prowl, are not as pure as your body, for the purpose of sacrifice.
त्वया देहे पवित्रत्वं प्राप्तं विष्णुप्रसादतः। अतः पवित्रं देहं त्वं यज्ञार्थं देहि मेऽसुर।२९।।
By you in frame, purity has been achieved by the grace of Visnu. Therefore, O Asura, you offer to me your pure frame for the purpose of a sacrifice.
गयासुर उवाच धन्योऽहं देवदेवेश यद्देहं प्रार्थ्यते त्वया। पितृवंशः कृतार्थो मे देहे यागं करोषि चेत्॥३० ।।
Gayāsura replied— I stands blessed, O gods of gods (Devadeveša) that by you, (my) body is being solicited as such. In case you offer a sacrifice over my body, the manes in my family shall be contented.
त्वयैवोत्पादितो देहः पवित्रस्तु त्वया कृतः। सर्वेषामुपकाराय यागोऽवश्यं भवत्विति।।३१।।
By you alone has been created this body (of mine) and by you only, it has been rendered sacred or sanctified. For the benefit of all, may the sacrifice comes to an existence.
इत्युक्तवा सोऽपतद्भूमौ श्वेतकल्पे गयासुरः। ब्रह्मा संभृतसंभारो मानसानृत्विजोऽसृजत्।।३२।।
Having said so, the demon Gaya, collapsed on the ground during the Svetakalpa. He adhered to the south-western quarter on the Kolāhala mountain.
इत्युक्त्वा सोऽपतद्भूमौ श्वेतकल्पे गयासुरः। नैऋतीं दिशमाश्रित्य तदा कोलाहले गिरौ।३३॥
Having turned the head in the north and having directed the feet in the south, Brahmā, having requisites gathered, created the mindborn sages.
Devas then started Yagna and thereafter Brahma asked to bring Sacrificial pole to fix in nearby lake (Brahmasara) and asked Dharma to place a slab on head of Gayasura. Gayasura, who was gullible, asked Devas to press the slab with their feet. All Devas with Rudra, Brahma and Vishnu stood on the slab to stabilize it.
आगत्य विष्णुः क्षीराब्धे: शिलायां संस्थितोऽभवत्। जनार्दनाभिधानेन पुण्डरीकेतिनामत्। शिलायां निश्चलार्थं हि स्वयमादिगदाधरः।५५।।
Having come from the milk ocean, Visnu himself, became stationed over the stone slab, with the name of Janārdana and also by the appellation of Pundarika. The primordial mace wielder himself stood there to steady the slab, for stabilising (the demon).
निश्चलार्थं पञ्चधाऽऽसीच्छिलायां प्रपितामहः। पितामहोऽथ फल्ग्वीशः केदारः कनकेश्वरः।५६।।
ब्रह्मा स्थितः स्वयं तत्र गजरूपी विनायकः। गयादित्यश्चोत्तराकोँ दक्षिणाकस्त्रिधा रविः।।५७।।
For stabilising (the demon Gaya), Brahmâ divided himself into five, viz. Prapitāmaha (Great-grandfather), Pitāmaha (Grandfather), Phalgvíša (Master of Phalgu), Kedara and Kanakešvara. Brahmā in the form of an elephant-normed Vināyaka (i.e. Ganeśa) stood there. Gayāditya, Uttarārka and Daksinārkathese were the three manifestations of Sun.
लक्ष्मीः सीताभिधानेन गौरी च मङ्गलाह्वया। गायत्री चैव सावित्री त्रिसंध्या च सरस्वती॥५८॥
Laksmi stood there in the name of Sitā, Gauri in the name of Mangalâ and Sarasvati stationed herself in three forms, viz. Gāyatri, Sávtiri and Sandhyā.
इन्द्रो बृहस्पतिः पूषा वसवोऽष्टौ महाबलाः। विश्वे देवाश्चाऽऽश्चिनेयौ (मारुतो विश्वनायकः। सयक्षोरगगन्धर्वास्तस्थुर्देवाः स्वशक्तिभि:।५९।।
Indra, Brhaspati, Püsan, the eight highly strong Vasus, Viśvedevas, the two Ašviní Devas, Maruts, the leader of the universe accompanied by Devas, Uragas and Gandharvas stood there along with their respective Saktis (powers).
आद्यया गदया चासौ यस्मादैत्य स्थिरीकृतः। स्थित इत्येव हरिणा तस्मादादिगदाधरः।।६०।।
Since the Daitya was brought to stagnation by the primordial club and Hari stood there, on that account, he became famous as ĀdiGadādhara.
Gayasura finally realized that it was a ploy to trick him. Devas then pleased with his sincere devotion gave him the boon that holy city would be named after him (as Gaya) and they (Devas) perennially would stay there.