We consider a gauged BL (Baryon number minus Lepton number) extension of the Standard Model (SM), which is anomaly free in the presence of three SM singlet Right Handed Neutrinos (RHNs). Associated with the gauge symmetry breaking, the RHNs acquire Majorana masses and then with the electroweak symmetry breaking, tiny Majorana masses for the SM(-like) neutrinos are naturally generated by the seesaw mechanism. As a result of the seesaw mechanism, the heavy mass eigenstates which are mainly composed of the SM-singlet RHNs obtain suppressed electroweak interactions through small mixings with the SM neutrinos. To investigate the seesaw mechanism, we study the pair production of heavy Majorana neutrinos through the gauge boson at the 250 GeV and 500 GeV International Linear Collider (ILC). Considering the current and prospective future bounds on the BL model parameters from the search for a resonant boson production at the Large Hadron Collider (LHC), we focus on a "smoking-gun" signature of the Majorana nature of the heavy neutrinos: a final state with a pair of same-sign, same-flavor leptons, small missing momentum, and four hadronic jets. We estimate the projected significance of the signature at the ILC.