The signal is called “clicked.” On_Clicked is a primitive operation of Gtk_Button_Record. See Gtk.Button package.
The first step is to choose the type of the emitter. It can be any antecedent of Gtk_Button_Record. E.g. it can be Gtk_Button_Record or Gtk_Widget_Record or GObject_Record. I frequently use GObject_Record for the sake of reusing the instantiation for signals having the same parameter profile (same user data). This will be the first parameter of the handler, which is usually irrelevant, which is why On_Clicked is useless.
The second step is to choose the right package in Gtk.Handlers. The choice depends on the signal parameters. Look for the clicked signal:
As you see there is no parameters. Self is the first parameter, user data is the second. The first parameter we selected in the step one. There is no result, so it must be a procedure. Ergo, the right package is User_Callback in Gtk.Handlers:
generic
type Widget_Type is new Glib.Object.GObject_Record with private;
type User_Type (<>) is private;
package User_Callback is
This package defines the handler profile:
type Simple_Handler is access procedure
(Widget : access Widget_Type'Class;
User_Data : User_Type);
This is exactly what we need as it matches the signal parameters. Now, we want to pass a record type as user data. Note that this would be totally useless, but you asked, so I respond… 
Let we have the record type declared as:
type My_Record_Type is record
I : Integer;
end record;
Then we instantiate the package like this:
package My_Record_Handlers is
new Gtk.Handlers.User_Callback (Gtk_Button_Record, My_Record_Type);
That is it!
We declare a procedure to handle the signal with the profile of Simple_Handler:
procedure My_Handler (Widget : access Gtk_Button_Record'Class;
User_Data : My_Record_Type) is
begin
... -- Do something useful on button clicked
end My_Handler;
Then we connect it to a button like this. Given My_Button (of Gtk_Widget) and My_Record (of My_Record_Type):
My_Record_Handlers.Connect (My_Button, "clicked", My_Handler'Access, My_Record);
Now in the real life. User_Data is almost always an access to a widget. Rather than record. Note that user data is marshalled = copied. So it must an access type anyway. The user data widget is usually a container that keeps the button. As I said before, you would derive your widget type from, say, Gtk_Grid_Record. Add custom members into the type extension, like Integer above. You do not want global data hanging around. So the custom widget is the right place to put any custom stuff into. Place the button into the grid and connect the handler from Initialize. Enjoy!